這類題是一類典型的two priority queue的題目累贤。維護(hù)兩個(gè)heap狱杰,一個(gè)MinHeap差凹,一個(gè)MaxHeap看疙。本解法中豆拨,MaxHeap的在奇數(shù)時(shí)會(huì)多一個(gè),奇數(shù)時(shí)返回MaxHeap的top(注意這里面的邏輯能庆,如果先往MaxHeap放施禾,那么MaxHeap就一定要多一個(gè))。另外注意搁胆,c++此題直接用multiset來實(shí)現(xiàn)priority_queue弥搞。如果priority_queue里面裝的是int,直接用multiset了
Leetcode 295:
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
size = 0;
}
void addNum(int num) {
size++;
if(m1.empty() || num < *m1.begin()){
m1.insert(num);
}
else{
m2.insert(num);
}
if(m1.size() > m2.size() + 1){
m2.insert(*m1.begin());
m1.erase(m1.begin());
}
if(m2.size() > m1.size()){
m1.insert(*m2.begin());
m2.erase(m2.begin());
}
}
double findMedian() {
if(size % 2 == 0){
return (*m1.begin() + *m2.begin()) / 2.0;
}
else{
return *m1.begin();
}
}
private:
multiset<int, greater<int>> m1; // max heap
multiset<int> m2; // min heap
int size;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
Lintcode 81:
Lintcode的題目要求稍有不同渠旁。偶數(shù)個(gè)時(shí)攀例,不是除平均,而是返回小的那個(gè)數(shù)顾腊。
class Solution {
public:
/**
* @param nums: A list of integers
* @return: the median of numbers
*/
void insertNumber(int num){
if(max_heap.empty() || num < *max_heap.begin()){
max_heap.insert(num);
}
else{
min_heap.insert(num);
}
if(max_heap.size() > min_heap.size() + 1){
min_heap.insert(*max_heap.begin());
max_heap.erase(max_heap.begin());
}
if(min_heap.size() > max_heap.size()){
max_heap.insert(*min_heap.begin());
min_heap.erase(min_heap.begin());
}
}
vector<int> medianII(vector<int> &nums) {
// write your code here
vector<int> ret;
if(nums.empty()) return ret;
for(auto it : nums){
insertNumber(it);
ret.push_back(*max_heap.begin());
}
return ret;
}
private:
multiset<int, greater<int>> max_heap;
multiset<int> min_heap;
};
Lintcode 360: Sliding Window Median
這道題也是用維護(hù)兩個(gè)heap來求解粤铭。難點(diǎn)在于要維護(hù)一個(gè)size = k的window,而不考慮其它元素杂靶。
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The median of the element inside the window at each moving
*/
void insert(int num){
if(m1.empty() || num <= *m1.begin()){
m1.insert(num);
}else{
m2.insert(num);
}
balanceSet();
}
void balanceSet(){
if(m1.size() > m2.size() + 1){
int cur = *m1.begin();
m1.erase(m1.begin());
m2.insert(cur);
}
if(m2.size() > m1.size()){
int cur = *m2.begin();
m2.erase(m2.begin());
m1.insert(cur);
}
}
void erase(int num){
if(num <= *m1.begin()){
m1.erase(m1.find(num));
}else{
m2.erase(m2.find(num));
}
balanceSet();
}
vector<int> medianSlidingWindow(vector<int> &nums, int k) {
// write your code here
vector<int> ret;
if(nums.empty() || k <= 0) return ret;
int idx = min(k, (int)nums.size());
for(int i=0; i<idx; i++){
insert(nums[i]);
}
ret.push_back(*m1.begin());
for(int i=idx; i<nums.size(); i++){
erase(nums[i - k]);
insert(nums[i]);
ret.push_back(*m1.begin());
}
return ret;
}
private:
multiset<int, greater<int>> m1;
multiset<int> m2;
};