给定一个未排序的数组 (x1, x2, ... ,xn), 其中每个元素关联一个权值:(w1, w2, ... ,wn), 且 . 请设计一个线性时间的算法, 在该数组中查找其带权中位数 xk, 满足:
image
思路
基于寻找无序数组第 k 小个数的 select 算法, 以 rand() 选出的 pivot 将数组分为三个部分, 并进行前后两部分权值总和的判断.
若 leftWeight <=0.5 && rightWeight <=0.5,pivot 为带权中位数
否则, 若 leftWeight> rightWeight, 则带权中位数在 pivot 左侧数组中, 将右侧权值赋给 pivot, 进行递归
leftWeight<= rightWeight 同理
伪代码
3.PNG
- #include <iostream>
- #include <iomanip>
- #include <stdlib.h>
- #include <time.h>
- #define N 5
- using namespace std;
- struct node
- {
- int value;
- double weight;
- };
- const int VALUE_MAX = 100;
- node INDEX[N] = { {1,0.6},{2,0.1},{5,0.1},{3,0.1},{4,0.1} };
- void Print(node *A, int len)
- {
- int i;
- for (i = 0; i <len; i++)
- cout << A[i].value << '\t';
- cout << endl;
- for (i = 0; i < len; i++)
- cout << A[i].weight << '\t';
- cout << endl;
- }
- // 返回选定的 pivot 中值
- int Partition(node *A, int begin, int end)
- {
- int Less = begin - 1, i;
- int pivotIndex = begin + rand() % (end - begin + 1);
- for (i = begin; i <= end; i++)
- {
- if (A[i].value < A[pivotIndex].value)
- {
- Less++;
- swap(A[Less], A[i]);
- }
- }
- swap(A[Less + 1], A[pivotIndex]);
- return Less + 1;
- }
- double getSumWeight(node*A, int begin, int end) {
- double sum = 0;
- for (int i = begin; i <= end; i++) {
- sum += A[i].weight;
- }
- return sum;
- }
- //
- int selectWeightedMedian(node* index, int begin, int end) {
- if (begin == end)
- return index[begin].value;
- if (end - begin == 1) {
- if (index[begin].weight == index[end].weight)
- return (index[begin].value + index[end].value) / 2;
- if (index[begin].weight> index[end].weight)
- return index[begin].value;
- else
- return index[end].value;
- }
- int midIndex = Partition(index, begin, end);
- double leftWeight = getSumWeight(index, begin, midIndex - 1);
- double rightWeight = getSumWeight(index, midIndex + 1, end);
- if (leftWeight <= 0.5&&rightWeight <= 0.5)
- return index[midIndex].value;
- else
- if (leftWeight> rightWeight) {
- index[midIndex].weight += rightWeight;
- return selectWeightedMedian(index, begin, midIndex);
- }
- else {
- index[midIndex].weight += leftWeight;
- return selectWeightedMedian(index, midIndex, end);
- }
- }
- int main(void) {
- srand((int)time(0));
- cout <<setprecision(3);
- int length, sum = 0;
- cout << "请输入数组长度:";
- cin>> length;
- node *index = new node[length + 1];
- int * weights = new int[length + 1];
- // 生成随机数据
- for (int i = 0; i < length; i++)
- {
- index[i].value = rand() % VALUE_MAX;
- do { weights[i] = rand() % VALUE_MAX; } while (weights[i] == 0);
- sum = sum + weights[i];
- }
- // 将权值规格化
- for (int i = 0; i < length; i++)
- index[i].weight = (double)weights[i] / sum;
- // 打印生成的数据
- Print(index, length);
- cout << "带权中位数为:" << selectWeightedMedian(index, 0, length - 1) << endl;
- system("pause");
- return 0;
- }
运行示例
运行示例
来源: http://www.jianshu.com/p/aae1518587ee