九章算法 | Google 面试题:滑动窗口的中位数
程序员文章站
2022-03-01 13:13:02
...
给定一个包含 n 个整数的数组,和一个大小为 k 的滑动窗口,从左到右在数组中滑动这个窗口,找到数组中每个窗口内的中位数。(如果数组个数是偶数,则在该窗口排序数字后,返回第 N/2 个数字。)
在线评测地址:LintCode 领扣
样例 1:
输入:
[1,2,7,8,5]
3
输出:
[2,7,7]
解释:
最初,窗口的数组是这样的:`[ | 1,2,7 | ,8,5]` , 返回中位数 `2`;
接着,窗口继续向前滑动一次。`[1, | 2,7,8 | ,5]`, 返回中位数 `7`;
接着,窗口继续向前滑动一次。`[1,2, | 7,8,5 | ]`, 返回中位数 `7`;
样例 2:
输入:
[1,2,3,4,5,6,7]
4
输出:
[2,3,4,5]
解释:
最初,窗口数组是这样的:`[ | 1,2,3,4, | 5,6,7]` , 返回中位数 `2`;
接着,窗口向前滑动一次.`[1,| 2,3,4,5 | 6,7]`,返回中位数 `3`;
接着,窗口向前滑动一次.`[1,2, | 3,4,5,6 | 7 ]`, 返回中位数 `4`;
接着,窗口向前滑动一次`[1,2,3,| 4,5,6,7 ]`, 返回中位数 `5`;
题解:
使用九章算法强化班中讲到的 HashHeap。即一个 Hash + Heap。 Hash 的 key 是 Heap 里的每个元素,值是这个元素在 Heap 中的下标。
要做这个题首先需要先做一下 Data Stream Median。这个题是只在一个集合中增加数,不删除数,然后不断的求中点。 Sliding Window Median,就是不断的增加数,删除数,然后求中点。比 Data Stream Median 难的地方就在于如何支持删除数。
因为 Data Stream Median 的方法是用 两个 Heap,一个 max heap,一个min heap。所以删除的话,就需要让 heap 也支持删除操作。 由于 Python 的 heapq 并不支持 logn 时间内的删除操作,因此只能自己实现一个 hash + heap 的方法。
总体时间复杂度 O(nlogk),n是元素个数,k 是 window 的大小。
public class Solution {
/*
* @param nums: A list of integers
* @param k: An integer
* @return: The median of the element inside the window at each moving
*/
PriorityQueue<Integer> maxHeap, minHeap;
public List<Integer> medianSlidingWindow(int[] A, int k) {
// write your code here
List<Integer> res = new ArrayList<Integer>();
int n = A.length;
if (n == 0) {
return res;
}
maxHeap = new PriorityQueue<Integer>(n, Collections.reverseOrder());
minHeap = new PriorityQueue<Integer>(n);
int i;
for (i = 0; i < n; ++i) {
if (maxHeap.size() == 0 || A[i] <= maxHeap.peek()) {
maxHeap.offer(A[i]);
}
else {
minHeap.offer(A[i]);
}
balance();
if (i - k >= 0) {
if (A[i - k] > maxHeap.peek()) {
minHeap.remove(A[i - k]);
}
else {
maxHeap.remove(A[i - k]);
}
}
balance();
if (i >= k - 1) {
res.add(maxHeap.peek());
}
}
return res;
}
private void balance() {
while (maxHeap.size() < minHeap.size()) {
maxHeap.offer(minHeap.poll());
}
while (minHeap.size() < maxHeap.size() - 1) {
minHeap.offer(maxHeap.poll());
}
}
}
更多题解参考:九章算法