m个有序数组求第k小的数字

最近遇到了这个问题，觉得挺有意思所以分享一下。不过不是面试遇到的.. 感觉这题目不知道解法的话短时间内完全做不出来（可以拿来面试时为难别人...）。

题目很简单，就是说有m个数组，长度不一定相等，总共合起来有N个元素，每个数组里的数字按从小到大已经排好序。给定k，要求在m * log(N)的时间内找到这所有N个数字中第k小的数字。

（这个问题的简单版本是一个LeetCode上的面试题：在m=2个有序数组中找中位数或者第k小的数字。不限制m之后就难了很多。）


----
注：m比较小而N很大，k可以任意取值，参考值m = 100，N = 10^9，k = N / 3。

这里贴一下问题的答案吧

这确实是一道比较难的题目，算法步骤略长，详细的解释与时间复杂度分析在这篇论文里：

Peter J. Varman, Scott D. Scheufler, Balakrishna R. Iyer, and Gary R. Ricard. 1991. Merging multiple lists on hierarchical-memory multiprocessors. J. Parallel Distrib. Comput. 12, 2 (June 1991)
https://github.com/jqdocshare/do ... tiseq_partition.pdf

文章里解决的是稍微更general一点的问题：将每个有序数组都partition为左右两边，使得所有的左边合起来正好是前k小的数字。里面的细节我就不翻写一遍了，因为很麻烦.. 得贴图才能解释清楚，不过如果有难以理解的地方我可以跟帖。

此外上述的partition版本是一个有实际用途的算法，它是并行多路归并排序算法（Parallel Multiway Mergesort）中重要的一步。
我遇到这个问题是因为想找一个单机多核排序的实现（C++，无GPU，workload是10亿量级的64位整数），然后发现gcc的并行多路归并排序是最有效使用多CPU（4核 ~ 20核）并且是最快的。此外gcc和tbb都有Parallel Balanced Quicksort，然而相对较慢。

这里是gcc的libstdc++中对该题算法的实现：https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/parallel/multiseq_selection.h#L388
用了260行代码

PS:
关于如何使用gcc的并行库：https://stackoverflow.com/questions/28520720/c-parallel-sort
我猜大多数人都没用过.. 但是如果你手上的电脑有4核或者8核，然后原来处理某些数据要等个10分钟，用下并行说不定就两三分钟了，还是很爽的。

FightForTomo 发表于 2017-6-24 22:35
错，我这个是KlogM。

O()时间复杂度和非定量K肯定不能有关系的。现在所谓的时间复杂度，都是算的是最大时间复杂度规模O()。

——————————
wiki:
在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。 这是一个代表算法输入值的字符串的长度的函数。 ... 例如，如果一个算法对于任何大小为n （必須比n0 大）的输入，它至多需要5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是O(n3)。

比较暴力,General(如果数组无序）一点的思路是建一个minHeap, 把N个元素塞进去，然后按k取值，这样时间复杂度是O(N+k)，空间要求是O(N); 不太符合题意  （当然把N个元素重新sort,就更暴力了）

既然我们知道了M， N和K的话， N是个很大的数字，意味着N/M 也是个大数，我们的思路最好不要跟N挂上钩。

每个数组都是有序的(假设是升序，降序的话方向需要反过来；无论如何变化都是从M个数组里，每个数组的最小数开始），我们改进一下思路。
首先建一个priority queue, 然后把M个数组的第一个元素Enqueue进去。大概思路跟LeetCode 上 378很像。不过378的输入是个matrix, 这里是个 jagged array-like的输入。
然后根据k来写一个while循环，做k次操作，每次只对priority queue的头一个元素, 头元素是largest element in the pq进行操作，下面的代码可能有Bug，我没检查，但大概思路是正确的：

while(K > 0)
{
    start = pq.First();
    int x = pq.First().Item1;   // index among in the M arrays
    int y = pq.First().Item2;   // index in the M[x] array
    pq.RemoveAt(0);             //Remove the first

    if(y < M[x].Length - 1)
    {
       pq.Insert(M[x][y+1]);
     }
     k--;
}
return start;

因为C#里没有pq, 只有SortedDictionary 和SortedList, 如果K很大的话(此处是N/3，优先考虑SortedDicitonary来满足最快的插入和删除performance =>都是O(logN))

时间复杂度是O(M*logK + k) , 空间上因为我们一直维持着一个size 为M 的优先队列，可以认为是O(M)
在大部分情况下， 是比O(M*logN)是要快一点的。不知道我的方法是否符合要求。
Updated:
经朋友提醒，时间复杂度应该是

M个数组第一项建堆 是O(M*logM), 然后取k次最小值是 K*logM 所以总的应该是 O(K*logM), 考虑到k可能会很大 所以应该是趋近于O(N*logM)

感觉确实有点难度啊。。。。。

思路可以从二分入手，细节还没想好

整个小堆，都塞堆里。NlogN

哦 MlogN啊。

那按照每个数组的第一个元素放到堆里。然后出堆堆时候就把出堆堆数组第一个数给删除了。再放回去。这样就MlogN了。

二分搜索咋搜？

FightForTomo 发表于 2017-6-24 20:18
整个小堆，都塞堆里。NlogN

哦 MlogN啊。

你这个不是NlogM吗

滚动的西瓜 发表于 2017-6-24 20:58
你这个不是NlogM吗

错，我这个是KlogM。

建一个最小堆，用堆排序

感觉思路是不是有点儿像median of medians？