第k个最小数字

debugcn 发表于 Dev

喜欢

假设我们有n个（1 <= n <= 10 ^ 3）大小为A1，A2，....的排序数组。（1 <= Ai <= 10 ^ 3）。我们需要根据这些数组的唯一组合来排序第k个最小的整数。是否有一种有效的方法来执行此操作，且复杂度小于O（A1 + A2 .. + An）？

可以解决类似于二进制搜索的问题吗？

PS：我在这里也有类似的问题，但是不明白如何将其扩展为独特的元素。

编辑1：我想你们中有些人误解了这个问题。让我们举个例子：N = 3，

A1 = 1，1，2，3

A2 = 6、7、9

A3 = 1、6、8

上述数组的唯一组合是{1、2、3、6、7、8、9}。现在假设我希望第二个元素应该返回2，第四个元素应该返回6。

用户名

可能在O(k n log n)：

使用每个数组中的最少元素进行最小堆操作。
重复k次数：
- 查看最小q堆中的最小元素，并记住它
- 从min-heap中提取，而最小值等于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

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。