c/c++带权中位数(O(n)复杂度)
2019-03-28 本文已影响1人
你猪头啊
题目:
给定一个未排序的数组(x1, x2, … ,xn),其中每个元素关联一个权值:(w1, w2, … ,wn),且。请设计一个线性时间的算法,在该数组中查找其带权中位数xk,满足:
在这里插入图片描述算法思想:
线性时间算法即为O(n),联想到之前写过的Select过程中的partition,选定一个pivot,将数组分成小于基数与大于基数的两部分,再计算两部分的权重和,如果左边的权重和大于右边的权重和,那么说明带权中位数在左边,对左边进行递归寻找,若左边权重和小于右边权重和,那么就说明,带权中位数在右边对右边进行递归寻找。
代码:
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
struct Node
{
int value;
double weight;
};
int partition(vector<Node>&A, int p, int r)
{
int less = p - 1, i;
int pivot = p + rand() % (r - p + 1);
for (i = p; i <= r; i++)
{
if (A[i].value < A[pivot].value)
{
less++;
swap(A[less], A[i]);
}
}
swap(A[less + 1], A[pivot]);
return less + 1;
}
int WeightedMedian(vector<Node>&A, int p, int r)
{
if (p == r)
return A[p].value;
if (r - p == 1)
{
if (A[p].weight == A[r].weight)
return (A[p].value + A[r].value) / 2;
if (A[p].weight > A[r].weight)
return A[p].value;
else
return A[r].value;
}
int q = partition(A, p, r);
double wl = 0, wr = 0;
for (int i = p; i <= q - 1; i++)
{
wl += A[i].weight;
}
for (int i = q + 1; i <= r; i++)
{
wr += A[i].weight;
}
if (wr < 0.5&&wl < 0.5)
return A[q].value;
else
{
if (wl > wr)
{
A[q].weight += wr;
WeightedMedian(A, p, q);
}
else
{
A[q].weight += wl;
WeightedMedian(A, q, r);
}
}
}
void Print(vector<Node>A)
{
for (int i = 0; i < A.size(); i++)
cout << A[i].value << " ";
cout << endl;
for (int i = 0; i < A.size(); i++)
cout <</*setprecision(2)<< */A[i].weight<<" ";
cout << endl;
}
void Initial(vector<int>&B,int n)
{
for (int i = 0; i < n; i++)
{
B.push_back(0);
}
}
int main(void)
{
int n, sum = 0;
cin >> n;
vector<Node>A;
vector<int>B;
A.resize(n);
B.resize(n);
Initial(B,n);
for (int i = 0; i < n; i++)
{
A[i].value = rand() % 100;
do { B[i] = rand() % 100; } while (B[i] == 0);
sum += B[i];
}
for (int i = 0; i < n; i++)
{
A[i].weight = (double)B[i] / sum;
}
Print(A);
cout << WeightedMedian(A, 0, n - 1);
system("pause");
return 0;
}