Cracking the coding interview--Q20.9

March 6, 2013
作者:Hawstein
出处:http://hawstein.com/posts/20.9.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

译文:

随机产生一些数传递给一个函数,写程序找出并维护这些数的中位数。

解答

方法一

最简单直观的方法是用一个足够大的数组A来维护这些数,使其按升序排列。 这样一来,可以用O(1)的时间找到中位数。下面是图示:

元素:1 3 5			元素:1 3 5 7
下标:0 1 2			下标:0 1 2 3
中位数:A[n/2]		中位数:(A[(n-1)/2] + A[n/2])/2

这种方法插入一个新来的元素需要O(n)的时间, 需要在原来有序的数组中找到一个合适的位置插入它,并把比它大的元素都向后移动1位。

方法二

用一个最大堆(或最小堆)来维护这些数。那么插入一个新元素需要O(logn)的时间, 比方法一要好。但取中位数需要先排序,时间复杂度O(nlogn)。

方法三

使用堆来维护数据是个不错的选择,因为插入一个新元素只需要O(logn)的时间, 但取中位数比较耗时,时间主要花在排序上。有没方法可以不排序呢? 我们知道,中位数是一个有序序列中排在中间的数,它左右两边的数相当。 从方法一的示意图可以看出,当数组大小n为奇数时,中位数就是有序序列中正中间那个数, 如果n为偶数,它是中间两个数的平均数。它只和序列中间的一个或两个数有关, 和其它的元素无关。那么,如果我用一个最大堆维护中位数左边的数(包含它), 用一个最小堆维护中位数右边的数。当n为偶数时,我只需要把左边的数最大那个, 和右边的数最小那个相加除以2即可。左边的最大数即最大堆的堆顶元素, 右边最小数即最小堆的堆顶元素。当n为奇数时,如果最大堆的元素比最小堆的元素多1, 则最大堆的堆顶元素是中位数;如果最小堆的元素比最大堆的元素多1, 则最小堆的堆顶元素是中位数。在插入新元素的时候,我们只要维护两个堆, 使其堆中元素的数量差别不超过1即可。

这样一来,插入新元素还是O(logn)的时间,而取中位数只需要O(1)的时间, 要优于方法一和方法二。

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
using namespace std;

class Median{
private:
    priority_queue<int,vector<int>,less<int> > max_heap;//左边的数
    priority_queue<int,vector<int>,greater<int> > min_heap;//右边的数

public:
    void Insert(int v);
    int GetValue();
};

void Median::Insert(int v){
    if(max_heap.empty() && min_heap.empty())
        max_heap.push(v);
    else if(!max_heap.empty() && min_heap.empty())
        max_heap.push(v);
    else if(max_heap.empty() && !min_heap.empty())
        min_heap.push(v);
    else{
        if(v < max_heap.top())
            max_heap.push(v);
        else
            min_heap.push(v);
    }
    //调整,保证两个堆的元素数量差别不大于1
    //不要用max_heap.size()-min_heap.size()>1
    //因为size返回的是unsigned类型,当左边相减得到一个负数时,本来为false
    //但会被转为一个大的正数,结果为true,出问题
    while(max_heap.size() > min_heap.size()+1){
        int data = max_heap.top();
        min_heap.push(data);
        max_heap.pop();
    }
    while(min_heap.size() > max_heap.size()+1){
        int data = min_heap.top();
        max_heap.push(data);
        min_heap.pop();
    }
}

int Median::GetValue(){//中位数为int,由于有除法,也可改为float
	if(max_heap.empty() && min_heap.empty())
        return (1<<31); //都为空时,返回int最小值
    if(max_heap.size() == min_heap.size())
        return (max_heap.top()+min_heap.top()) / 2;
    else if(max_heap.size() > min_heap.size())
        return max_heap.top();
    else
        return min_heap.top();
}

int main(){
    srand((unsigned)time(0));
    Median md;
    vector<int> vi;
    int num = rand() % 30; //数量是30以内的随机数
    for(int i=0; i<num; ++i){
        int data = rand() % 100; //元素是100内的数
        vi.push_back(data);
        md.Insert(data);
    }
    sort(vi.begin(), vi.end());
    for(int i=0; i<num; ++i)
        cout<<vi.at(i)<<" "; //排序的序列
    cout<<endl<<md.GetValue()<<endl; //中位数
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview