title: 带权中位数
date: 2021-04-12
tags: 算法
categories: 学习
mathjax: true

带权中位数

1.题目描述

2.思想

基于寻找无序数组第k小个数的select算法，以rand()选出的pivot将数组分为三个部分，并进行前后两部分权值总和的判断。
若leftWeight <=0.5 && rightWeight <=0.5，pivot为带权中位数
否则，若leftWeight > rightWeight，则带权中位数在pivot左侧数组中，将右侧权值赋给pivot，进行递归
leftWeight<= rightWeight同理

原文链接：https://blog.csdn.net/qq_36544876/article/details/88866480

3.代码

#include"iostream"
#include"cstdlib"
using namespace std;
class term
{
public:
    double num;
    double weight;
};
class Term_array
{
public:
    term *elmt;
    int num;
    int head;
    int tail;
    Term_array(int Element_num)
    {
        num = Element_num;
        head = 0;
        tail = num - 1;
        elmt = new term[Element_num];//记得中括号
        for (int i = 0; i < Element_num; i++)
        {
            elmt[i].num = 0;
            elmt[i].weight = 0;
        }
    }
    ~Term_array()
    {
        if (elmt)
            delete[]elmt;
    }
};
/*测试用
void print(Term_array &arr)
{
    for (int i =0; i < arr.num; i++)
    {
        cout << arr.elmt[i].num << ' ' << arr.elmt[i].weight << ' ' << endl;
    }
    cout << "-----------" << endl;
}
*/
void swaparr(int ele1, int ele2, Term_array &arr)
{
    double num_tmp = arr.elmt[ele1].num;
    double weight_tmp = arr.elmt[ele1].weight;
    arr.elmt[ele1].num = arr.elmt[ele2].num;
    arr.elmt[ele1].weight = arr.elmt[ele2].weight;
    arr.elmt[ele2].num = num_tmp;
    arr.elmt[ele2].weight = weight_tmp;
}
void copyele(int ele1, int ele2, Term_array &arr)
{
    arr.elmt[ele1].num = arr.elmt[ele2].num;
    arr.elmt[ele1].weight = arr.elmt[ele2].weight;
}
int partition(int p,Term_array &arr)//以下标p开始划分
{
    int start = arr.head;
    swaparr(start, p, arr);//与0号交换位置
    term tmp = arr.elmt[start];
    int l =arr.head; int r = arr.tail;
    while (l < r)
    {
        while (l < r&&arr.elmt[r].num >= tmp.num)
        {
            r--;
        }
        copyele(l, r, arr);
        while (l < r&&arr.elmt[l].num <= tmp.num)
        {
            l++;
        }
        copyele(r, l, arr);
    }
    arr.elmt[l] = tmp;
    return l;
}
int isWm(int &l, Term_array &arr)
{
    int flag = 0;
    double lsum = 0.0;
    double rsum = 0.0;
    for (int i = 0; i < l; i++)
        lsum += arr.elmt[i].weight;
    for (int i = l + 1; i < arr.num; i++)
        rsum += arr.elmt[i].weight;
    if (lsum<=0.5&&rsum<=0.5)
        flag = 0;
    else if (lsum < rsum)
        flag = -1;
    else if(lsum>rsum)
        flag = 1;
    return flag;
}
int main()
{
    int Element_Num = 0;
    int Wm = 0;
    cin >> Element_Num;
    Term_array arr(Element_Num);
    for (int i = arr.head; i <= arr.tail; i++)
    {
        cin >> arr.elmt[i].num;
    }
    for (int i = arr.head; i <= arr.tail; i++)
    {
        cin >> arr.elmt[i].weight;
    }
    if (arr.num > 1)
    {
        int rand_num = (rand() % (arr.tail - arr.head + 1) + arr.head);//生成随机数
        int pos = partition(8, arr);//随机开始划分
    //接下来判断是否是带权中位数
        int flag = 0;
        while (1)
        {
            flag = isWm(pos, arr);
            if (flag == 0)//恰好是带权中位数
            {
                Wm = arr.elmt[pos].num;
                break;
            }
            else if (flag == -1)//右边大于左边,在右边找
            {
                arr.head = pos + 1;
                rand_num = (rand() % (arr.tail - arr.head + 1) + arr.head);
                pos = partition(rand_num, arr);
            }
            else if (flag == 1)
            {
                arr.tail = pos - 1;
                rand_num = (rand() % (arr.tail - arr.head + 1) + arr.head);
                pos = partition(rand_num, arr);
            }
        }
    }
    else
        Wm = arr.elmt[0].num;
    cout << Wm << endl;
    return 0;
}