[mitbbs面经思路][Google] k largest elements

mitbbs google 最新算法题讲解,sliding window 中查找top K元素。

题目引用

Find k-largest elements in a sliding window

A long array A[] with size n is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Find top k elements in the sliding window when it moves to each n positions.

小编解答

题目类型TAG:堆,树,堆栈

正如发帖人所述,这道题目是 Sliding Window Maximum 的变种。如果只是要求最大的元素,那么可以通过原题 讲解中的堆栈解法以O(n) 的复杂度解决。 当要求输出所有sliding window 的top k 大的元素时,通过直觉,我们可以知道总共有 k*n次输出,所以最少 O(k*n)的时间复杂度是逃不掉的。在这里,包子以多种思路来讲解此题,希望大家能有所收获。

惯性思路:

每次一讲到top k元素的时候,是不是最小堆的想法就突然从你的脑子里面冒出来了?的确,一般来说从长度为n的元素的中取前k大的元素(k 远小于 n)的时候,最小堆可以以O(n log k) 的复杂度取得不错的结果。可惜的是,在此题中如果要如此炮制,恐怕需要在每个sliding window 中分别进行一次复杂度为w * log(k)的最小堆操作,总共时间复杂度达到了 O(n * w * log(k))。

要注意的是,我们不可以用一个最小堆来寻找所有sliding window的最大 k 个元素们。原因是最小(大)堆算法只能往堆里面增加元素,而这题里当sliding window 移动的时候,还会需要减少元素。

常规思路

维护一棵sliding window大小的平衡二叉查找树或许是一个比较常规也是很实际的方法。我们可以通过倒着遍历树中最后的k个元素来取得当前树所代表的sliding window 里面的最大的k个元素。当sliding 窗口移动的时候我们往树中分别删除一个刚出window的元素并增加一个新进入window 的元素。由于是一个平衡二叉树,每次变更操作耗时是O(log(w)),而遍历k个元素的耗时是O(k),所以对整个数组操作的总耗时是 O(n*(k + log(w)))。

说实话,在实际中,这是一个非常完美的算法,因为它达到了一个非常好的实现复杂度和运行时效率的平衡。log(w)可以几乎看成是一个常数,因此其算法复杂度逼近我们之前预测的最低 O(n*k)。在实现上,我们可以用编程语言库里面的TreeMap,完全成熟,不易出错。

启发思路

因为是面试题,我们不妨讨论一些取巧的方法。我们知道,在求最大元素的原题解法里面,我们可以轻松得到O(n)的复杂度,那么,我们是否可以通过把原题跑 k 遍来得到top k个元素呢?如果真的可以,那么我们的复杂度就成了真正的 O(n * k) 了。让我们来顺着这个思路往下想:我们对数组进行K次扫描,每一次扫描的时候都按之前O(n)的方法取得移动 window 的最大值,并把那个取到的最大元素改成无穷小,那么下一次扫描的时候就可以求得第二大的元素了。

这样说来貌似可行,其实还有一些细节需要tweak。比如给定数组如下,
[2 3 5 9 0]
移动窗口长度为 3。当窗口在最左边的位置时,窗口中最大元素为5,那么我们是否可以在第一次扫描结束时简单地将5编程 -infinity呢?答案显然是否定的,因为当窗口移到第二个位置的时候,9变成了最大值,这时候被我们改成-infinity 的5 还得回来。

根据这个思路,希望同学们继续思考,欢迎发信到baozidiscussion@googlegroups.com 讨论。

博客推送