博客

查找C++无序数列中位数

1.将无序数列转化为有序数列，然后直接通过索引找到中位数
2.已知中位数 要求左边小于（大于）中位数，右边大于（小于）中位数，且左边数列大小等于右边数列大小 。 而对左边数列或者右边数列数值的排列顺序无要求。
所以，我们可以采用优先队列进行解决。

代码实现

#include<iostream>
#include<queue>//优先队列
#include<vector>
#include<assert.h>
#include<list>

//利用优先队列实现，使得堆顶左边都比堆顶大，其余未入队列的数据全都比堆顶小，队列的大小应该为一半。

using namespace std;

template<class T>
T findMidle(const T *arr,int size)
{
    assert(arr);
    int len=0;
    //优先队列
    priority_queue<int,vector<int>,greater<int> > q;//从大到小

    if(size&1)//奇数
    {
        len=(size+1)/2;

        //将局部数据放入队列，pop为局部最小
        for(int i=0;i<len;++i)
        {
            q.push(arr[i]);
        }

        //大于堆顶的push进入队列，使得堆顶的左边比堆顶大，右边比堆顶小，此时堆顶为中位数
        for(int i=len;i<size;++i)
        {
            if(q.top()<arr[i])
            {
                q.pop();
                q.push(arr[i]);
            }
        }

        return q.top();

    }
    else//偶数
    {
        len=size/2;
        //优先队列
        //priority_queue<int,vector<int>,greater<int>()> q;//从大到小

        //将局部数据放入队列，pop为局部最小
        for(int i=0;i<len;++i)
        {
            q.push(arr[i]);
        }

        //大于堆顶的push进入队列，使得堆顶的左边比堆顶大，右边比堆顶小，此时堆顶为中位数

        int flag=0;//存储最后一次pop出来的数据
        for(int i=len;i<size;++i)
        {
            if(q.top()<arr[i])
            {
                flag=q.top();
                q.pop();
                q.push(arr[i]);
            }
        }

        return (q.top()+flag)/2;
    }
    
}

void test01()
{
    //准备数据
    int arr[]={10,20,12,16,15,4,8,10};//偶数重复,  4,8,10,10,12,15,16,20 中位数：11
    
    //int arr1[]={10,20,12,16,15,4,10};//奇数重复， 中位数：12

    int len=sizeof(arr)/sizeof(int);

    int ret=findMidle<int>(arr,len);

    cout<<"the middle is : "<<ret<<endl;
}

int main()
{
    test01();
    system("pause");
    return 0;
}