问题描述:
初阶:有两个数组A和B,假设A和B已经有序(从大到小),求A和B数组中所有数的第K大。
进阶:有N台机器,每台机器上有一个有序的大数组,需要求得所有机器上所有数中的第K大。注意,需要考虑N台机器的并行计算能力。
思路:
初阶:比较A[k/2]和B[k/2],如果A[k/2]>=B[k/2]那么A的前k/2个数一定都在前k-1大中,将A数组前k/2个数扔掉,反之扔掉B的前k/2个数。将k减小k/2。重复上述操作直到k=1。比较A和B的第一个数即可得到结果。时间复杂度O(logk)
进阶:二分答案S,将S广播给每台机器,每台机器用二分法求得有多少比该数小的数。汇总结果后可判断是该将S往上还是往下调整。
面试官角度:
初阶问题是一个难度比较大的算法题。需要有一定的算法训练功底。主要用到的思想是递归。首先容易想到的方法是合并两个数组(见面试题5,有序数组的合并),这样复杂度为O(k),那么答出这个以后,面试官会问你,还有更好的方法么?这个时候就要往O(logk)的思路去想,O(logk)就意味着需要用一种方法每次将k的规模减小一半,于是想到,每次要扔掉一个数组或两个数组中的k/2个数,于是想到去比较A[k/2]和B[k/2],仔细思考比较结果,然后想到较大的那一方的前k/2个数一定都在前k-1大的数中, 所以可以扔掉。
进阶问题的考察点是逆向思维。二分答案是一种常见的算法思路(见面试题2 抄书问题),所以当你想不出题目的时候,往往可以试试看是否可以二分答案。因为需要发挥N台机器的并行计算能力,所以想到让每台机器互不相关的做一件事情,然后将结果汇总来判断。
一般来讲,面试中问题这两个题目,说明职位对算法能力的要求还是比较高的。
参考资料:/problem/8/