第 k 个最小的数

Question

假设我们有 n (1<=n<=10^3) 个大小为 A1、A2、.... An 的已排序数组。 (1<=艾<=10^3)。我们需要从这些数组的 unique 组合中对 kth smallest integer 进行排序。有没有一种复杂度低于 O(A1 + A2.. + An) 的有效方法？

可以解决类似二分查找的问题吗？

PS：我这里有一个 similar problem，但不明白如何为独特的元素扩展它。

编辑 1： 我认为你们中的一些人误解了这个问题。让我们举个例子： N = 3,

A1 = 1, 1, 2, 3

A2 = 6, 7, 9

A3 = 1, 6, 8

以上数组的唯一组合是{1, 2, 3, 6, 7, 8, 9}。现在假设我想要第二个元素它应该 return 2 而对于第四个元素它应该 return 6.

Answer 1

是否有space要求，或者数组中的数字是否可以重复？

如果没有，您可以创建 2 个排序集：uniques 和 nonUniques。添加数组时，您遍历数组并将其数字添加到 2 个排序集合中，如下所示：

如果 nonUniques 中存在新号码，则跳过它
如果一个数字存在于 uniques 中，将其从 uniques 中删除并将其添加到 nonUniques
否则将 nww 号码添加到 uniques

然后你可以立即在排序后的uniques集合中查找第k小的数字。

Answer 2

在O(k n log n)中是可能的：

用每个数组中的最小元素创建一个最小堆。
重复k次：
- 查看min-heap中的最小元素q并记住
- 当最小值等于 q 时从最小堆中提取。
- 对于每个提取的元素，将第一个大于q的元素从相应的数组中放入
答案是最小堆中的最小元素

Python代码：

import heapq
import bisect

def kth(A, k):
    h = []

    for idx,a in enumerate(A):
        if len(a) > 0:
            heapq.heappush(h, (a[0], idx))

    for i in xrange(k):
        if len(h) == 0:
            return None

        val, _ = h[0]

        while (len(h) > 0) and (h[0][0] == val):
            _, idx = heapq.heappop(h)
            nxt = bisect.bisect_right(A[idx], val)
            if nxt < len(A[idx]):
                heapq.heappush(h, (A[idx][nxt], idx))

    if len(h) > 0:
        return h[0][0]
    return None

第 k 个最小的数

kth smallest number

algorithm

binary-search