题目
原文：
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
2
3
元素：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)的时间， 要优于方法一和方法二。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#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
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/03/06/20.9/
