leetcode面试题8 第k大的数

leetcode面试题8 第k大的数
初阶：有两个数组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台机器的并行计算能力，所以想到让每台机器互不相关的做一件事情，然后将结果汇总来判断。
http://lixinzhang.github.io/jiu-zhang-suan-fa-mian-shi-ti-zong-jie.html

int FindK(vector<vector<int> > & mq, int N, int k)
{
    int ans_upper = INT_MAX;
    int ans_lower = INT_MIN;
    int sum_len = 0;
    while(sum_len != k)
    {
        ans = ans_lower + (ans_upper - ans_lower) /2;
        for (int i=0; i<N; i++)
        {
           sum_len += left_count_binarySearch(mq[i], ans);
        }
        if (sum_len > k) ans_upper = ans;
        if (sum_len < k) ans_lower = ans;
    }
    return ans;
}

http://www.cnblogs.com/zhjp11/archive/2010/02/26/1674227.html

          《编程之美》2.5节课后习题：
           1. 如果需要找出N个数中最大的K个不同的浮点数呢？比如，含有10个浮点数的数组（1.5，1.5，2.5，3.5，3.5，5，0，- 1.5，3.5）中最大的3个不同的浮点数是（5，3.5，2.5）。
           解答：上面的解法均适用，需要注意的是浮点数比较时和整数不同，另外求hashkey的方法也会略有不同。
           2. 如果是找第k到第m（0<k<=m<=n)大的数呢？
           解答：如果把问题看做m-k+1个第k大问题，则前面解法均适用。但是对于类似前k大这样的问题，最好使用解法5或者解法7，总体复杂度较低。
       3. 在搜索引擎中，网络上的每个网页都有“权威性”权重，如page rank。如果我们需要寻找权重最大的K个网页，而网页的权重会不断地更新，那么算法要如何变动以达到快速更新（incremental update）并及时返回权重最大的K个网页？
提示：堆排序？当每一个网页权重更新的时候，更新堆。还有更好的方法吗？
       解答：要达到快速的更新，我们可以解法5，使用映射二分堆，可以使更新的操作达到O(logn)

       4. 在实际应用中，还有一个“精确度”的问题。我们可能并不需要返回严格意义上的最大的K个元素，在边界位置允许出现一些误差。当用户输入一个query的时候，对于每一个文档d来说，它跟这个query之间都有一个相关性衡量权重f (query, d)。搜索引擎需要返回给用户的就是相关性权重最大的K个网页。如果每页10个网页，用户不会关心第1000页开外搜索结果的“精确度”，稍有误差是可以接受的。比如我们可以返回相关性第10 001大的网页，而不是第9999大的。在这种情况下，算法该如何改进才能更快更有效率呢？网页的数目可能大到一台机器无法容纳得下，这时怎么办呢？

      提示：归并排序？如果每台机器都返回最相关的K个文档，那么所有机器上最相关K个文档的并集肯定包含全集中最相关的K个文档。由于边界情况并不需要非常精确，如果每台机器返回最好的K’个文档，那么K’应该如何取值，以达到我们返回最相关的90%*K个文档是完全精确的，或者最终返回的最相关的K个文档精确度超过90%（最相关的K个文档中90%以上在全集中相关性的确排在前K），或者最终返回的最相关的K个文档最差的相关性排序没有超出110%*K。
      解答：正如提示中所说，可以让每台机器返回最相关的K'个文档，然后利用归并排序的思想，得到所有文档中最相关的K个。 最好的情况是这K个文档在所有机器中平均分布，这时每台机器只要K' = K / n （n为所有机器总数）；最坏情况，所有最相关的K个文档只出现在其中的某一台机器上，这时K'需近似等于K了。我觉得比较好的做法可以在每台机器上维护一个堆，然后对堆顶元素实行归并排序。

       5. 如第4点所说，对于每个文档d，相对于不同的关键字q1, q2, …, qm，分别有相关性权重f（d, q1），f（d, q2）, …, f（d, qm）。如果用户输入关键字qi之后，我们已经获得了最相关的K个文档，而已知关键字qj跟关键字qi相似，文档跟这两个关键字的权重大小比较靠近，那么关键字qi的最相关的K个文档，对寻找qj最相关的K个文档有没有帮助呢？

解答：肯定是有帮助的。在搜索关键字qj最相关的K个文档时，可以在qj的“近义词”相关文档中搜索部分，然后在全局的所有文档中在搜索部分。

http://www.w2bc.com/Article/72564
Read full article from leetcode面试题8 第k大的数