Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )
Have you met this question in a real interview?
Yes
Example
For array[1,2,7,8,5], moving window size k = 3. return[2,7,7]
At first the window is at the start of the array like this
[ | 1,2,7 | ,8,5], return the median2;
then the window move one step forward.
[1, | 2,7,8 | ,5], return the median7;
then the window move one step forward again.
[1,2, | 7,8,5 | ], return the median7;
O(nlog(n)) time
class Solution {
public:
/\*\*
\* @param nums: A list of integers.
\* @return: The median of the element inside the window at each moving
\*/
vector<int> medianSlidingWindow\(vector<int> &nums, int k\) {
// write your code here
vector<int> res;
if \(nums.size\(\) < k\) {
return res;
}
multiset<int> maxHeap;
multiset<int> minHeap;
for \(int i = 0; i < k - 1; ++i\) {
if \(maxHeap.empty\(\) \|\| nums\[i\] <= \*maxHeap.rbegin\(\)\) {
maxHeap.insert\(nums\[i\]\);
} else {
minHeap.insert\(nums\[i\]\);
}
if \(!isBalanced\(maxHeap.size\(\), minHeap.size\(\)\)\) {
balance\(maxHeap, minHeap\);
}
}
for \(int i = k - 1; i < nums.size\(\); ++i\) {
// add cur
if \(maxHeap.empty\(\) && minHeap.empty\(\)\) {
maxHeap.insert\(nums\[i\]\);
} else if \(maxHeap.empty\(\)\) {
minHeap.insert\(nums\[i\]\);
} else if \(minHeap.empty\(\)\) {
maxHeap.insert\(nums\[i\]\);
} else {
if \(nums\[i\] <= \*maxHeap.rbegin\(\)\) {
maxHeap.insert\(nums\[i\]\);
} else {
minHeap.insert\(nums\[i\]\);
}
}
if \(!isBalanced\(maxHeap.size\(\), minHeap.size\(\)\)\) {
balance\(maxHeap, minHeap\);
}
// save the median
if \(maxHeap.size\(\) >= minHeap.size\(\)\) {
res.push\_back\(\*maxHeap.rbegin\(\)\);
} else {
res.push\_back\(\*minHeap.begin\(\)\);
}
// delete first one out of window
if \(!maxHeap.empty\(\) && nums\[i-\(k-1\)\] <= \*maxHeap.rbegin\(\)\) {
maxHeap.erase\(maxHeap.find\(nums\[i-\(k-1\)\]\)\);
} else {
minHeap.erase\(minHeap.find\(nums\[i-\(k-1\)\]\)\);
}
if \(!isBalanced\(maxHeap.size\(\), minHeap.size\(\)\)\) {
balance\(maxHeap, minHeap\);
}
}
return res;
}
private:
bool isBalanced\(int size1, int size2\) {
return abs\(size1 - size2\) <= 1;
}
void balance\(multiset<int> &maxHeap, multiset<int> &minHeap\) {
if \(maxHeap.size\(\) > minHeap.size\(\)\) {
minHeap.insert\(\*maxHeap.rbegin\(\)\);
maxHeap.erase\(prev\(maxHeap.end\(\)\)\);
} else {
maxHeap.insert\(\*minHeap.begin\(\)\);
minHeap.erase\(minHeap.begin\(\)\);
}
}
};