題目：

給定一個未排序的數(shù)組(x1, x2, … ,xn)，其中每個元素關聯(lián)一個權值：(w1, w2, … ,wn)，且。請設計一個線性時間的算法，在該數(shù)組中查找其帶權中位數(shù)xk，滿足：

在這里插入圖片描述

算法思想：

線性時間算法即為O（n），聯(lián)想到之前寫過的Select過程中的partition，選定一個pivot，將數(shù)組分成小于基數(shù)與大于基數(shù)的兩部分，再計算兩部分的權重和，如果左邊的權重和大于右邊的權重和，那么說明帶權中位數(shù)在左邊，對左邊進行遞歸尋找，若左邊權重和小于右邊權重和，那么就說明，帶權中位數(shù)在右邊對右邊進行遞歸尋找。

代碼：

#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;
}