給定一個(gè)未排序的數(shù)組(x1, x2, … ,xn)吓歇，其中每個(gè)元素關(guān)聯(lián)一個(gè)權(quán)值：(w1, w2, … ,wn)孽水，且 。請?jiān)O(shè)計(jì)一個(gè)線性時(shí)間的算法城看，在該數(shù)組中查找其帶權(quán)中位數(shù)xk女气，滿足：

image

思路

基于尋找無序數(shù)組第k小個(gè)數(shù)的select算法，以rand()選出的pivot將數(shù)組分為三個(gè)部分测柠，并進(jìn)行前后兩部分權(quán)值總和的判斷炼鞠。
若leftWeight <=0.5 && rightWeight <=0.5缘滥，pivot為帶權(quán)中位數(shù)
否則，若leftWeight > rightWeight谒主，則帶權(quán)中位數(shù)在pivot左側(cè)數(shù)組中朝扼，將右側(cè)權(quán)值賦給pivot，進(jìn)行遞歸
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 << "請輸入數(shù)組長度:";
    cin >> length;
    node *index = new node[length + 1];
    int * weights = new int[length + 1];
    //生成隨機(jī)數(shù)據(jù)
    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];
    }
    //將權(quán)值規(guī)格化
    for (int i = 0; i < length; i++)
        index[i].weight = (double)weights[i] / sum;
    //打印生成的數(shù)據(jù)
    Print(index, length);
    cout << "帶權(quán)中位數(shù)為:" << selectWeightedMedian(index, 0, length - 1) << endl;
    system("pause");
    return 0;
}

運(yùn)行示例

運(yùn)行示例