随机生成一些数,写一个程序找到这些数的中位数,并且当新的数生成的时候能够维护中位数。
思路:
直观的思路是排序或者用划分的思路找中位数,但是这些都是在数组固定的情况下,现在的情况是随时可能有新的数产生。
1、可以用一个足够大的数组来维护这些数,然后每产生一个数就将它插入到数组中并保持有序,这样插入一个数的复杂度为O(n),取中位数的复杂度为O(1)。
2、可以用一个堆来位数这些数,插入一个数的复杂度为O(logn),但取中位数要先堆排序,复杂度为O(nlogn)。
3、可以用一个大顶堆maxheap和一个小顶堆minheap来维护中位数。大顶堆存放小于等于中位数的数,小顶堆存放大于等于中位数的数。在插入的时候随时保持 maxheap.size() == minheap.size() 或 maxheap.size() == minheap.size() + 1,这样中位数的值为 (maxheap.top() + minheap.top())/2 或 maxheap.top(),即取中位数的复杂度为O(1)。
#include <iostream> #include <queue> #include <assert.h> #include <time.h> using namespace std; class CMedian { public: void Insert(int v); int GetMedian(); private: priority_queue<int> max; priority_queue< int, vector<int>, greater<int> > min; }; void CMedian::Insert(int num) { if (max.size() == min.size()) { if (max.empty()) max.push(num); else { if (num <= min.top()) max.push(num); else { max.push(min.top()); min.pop(); min.push(num); } } } else { if (num >= max.top()) min.push(num); else { min.push(max.top()); max.pop(); max.push(num); } } } int CMedian::GetMedian() { assert(!max.empty()); if (max.size() == min.size()) return max.top() + ((min.top() - max.top()) >> 1); else return max.top(); } int main() { srand((unsigned)time(0)); CMedian m; vector<int> ivec; int num = rand() % 50; for (int i = 0; i < num; ++i) { int value = rand() % 1000; ivec.push_back(value); m.Insert(value); } sort(ivec.begin(), ivec.end()); for (int i = 0; i < ivec.size(); ++i) cout << ivec[i] << endl; cout << ivec[(num-1)/2] << " " << ivec[num/2] << endl; cout << m.GetMedian() << endl; return 0; }