题目来源
设计一个数据结构找中位数。
我一开始想的是用一个vector，然后addNum的时候，二分，找到合适的位置，插入，维持一个有序的状态，可以AC，但是比较麻烦，代码也比较长。
代码如下：
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
int n = nums.size();
if (n == 0) {
nums.push_back(num);
return;
}
int l = 0, r = n - 1;
int mid;
while (l <= r) {
mid = (l + r) / 2;
if (nums[mid] == num) {
nums.insert(nums.begin()+mid+1, num);
return;
}
else if (nums[mid] > num)
r = mid - 1;
else
l = mid + 1;
}
if (nums[mid] > num)
nums.insert(nums.begin()+mid, num);
else
nums.insert(nums.begin()+mid+1, num);
}
double findMedian() {
int n = nums.size();
int mid = (n - 1) / 2;
if (n % 2 != 0)
return nums[mid];
else
return (nums[mid] + nums[mid+1]) / 2.0;
}
private:
vector<int> nums;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
看了下讨论区，可以直接用优先队列来做，代码如下：
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
small.push(num);//注意这里每个元素需要先入small再入large，否则可能导致大的在small，如1，2，3
large.push(-small.top());
small.pop();
if (large.size() > small.size()) {
small.push(-large.top());
large.pop();
}
}
double findMedian() {
if ((small.size() + large.size()) % 2 == 0)
return (small.top() - large.top()) / 2.0;
else
return small.top();
}
private:
priority_queue<int> small, large;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
