今日面试题:又见Google搜索之星

给定一批查询日志,数量为n。其中,有的查询出现了多于n/3次,请在线性时间内,找到所有满足条件的查询。

须弥之镜面试题分析

原题:

有k个有序的数组,请找到一个最小的数字范围。使得这k个有序数组中,每个数组都至少有一个数字在该范围中。

例如:

1: 4, 10, 15, 24, 26

2: 0, 9, 12, 20

3: 5, 18, 22, 30

所得最小范围为[20,24],其中,20在2中,22在3中,24在1中。

分析:

遇到一个题目,我们要通过分析找到突破口。这个题目的突破口是什么呢?其实比较好找。就是“有序”,而且k个数组都是有序的,那么我们脑海里就会浮现出各种可以尝试的方法:可以对有序的数组进行二分查找、可以对多个有序的数组进行归并排序,生成一个有序的数组等等。

那这个题目选择哪个方法继续尝试呢?那我们再分析一下要解决的问题。找到一个最小的范围,每一个有序数组中,都至少有一个元素在这个范围中。找到这样一个范围并不难,可是如何确定最小的范围呢?最终得到的最小的范围,至少包含三个元素,并且在所有数组整体的排序中,是相邻的。假设最小范围是[a, b, c],a < b < c。 c-a是最小的。并且,a,b,c来自不同的有序数组。还有一种情况是[a,b,d,c],a,b,c不是紧邻的,中间有一个d即: a< d < c。这时,d只能是来自b所在的数组,如下分析:

d来自a所在的数组,那么应有更短的范围c - d

d来自c所在的数组,那么应有更短的范围d - a

d来自b所在的数组,范围大小是不变的,就是无论是考虑d,还是考虑b。都没有影响。

从上面的分析,我们得出,只需要考虑在最终的排序中,考虑邻近的、并且来自不同有序数组的元素,作为备选的范围。那么该怎么样做到只考虑临近的、并且来自不同的有序数组的元素呢?这里就用到了归并排序的思想。以原题中的例子为例,假设有三个指针指,p1,p2,p3,分别指向三个数组的第一个元素:

步骤 指针当前值 最大值 最小值 min_range_value 移动指针
1 4,0,5 5 0 5 p2
2 4,9,5 9 4 5 p1
3 10,9,5 10 5 5 p3
4 10,9,18 18 9 9 p2
5 10,12,18 18 10 8 p1
6 15,12,18 18 12 6 p2
7 15,20,18 20 15 5 p1
8 24,20,18 24 18 6 p3
9 24,20,22 24 20 4 p2
end

结束是因为第二个数组已经没有元素可以再进行遍历了。最终得到最小的min_range_value为4,即为题目例子的答案。

上面这个方法,通过归并排序的思想,确保每次都是k个来自不同的数组的元素进行比较,得到最大值、最小值。就可以得到一个范围,包含了所有数组中的数字。

这个题的著名变种是从网页中产生包含所有查询词的最小的摘要。如果你 面过Google,你应该听说过这题。

本文来自微信:待字闺中,2013-07-17发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。