从n个已排序数组中找到第k小的数字

Question

从n个已排序数组中找到第k小的数字

arraysalgorithmdata-structuresmerge

25

所以，你有n个已排序的数组（长度不一定相等），你需要返回合并所有n个已排序数组后第k小的元素。

我已经尝试了很长时间，包括其他变体，但到目前为止，我只对两个长度相等的数组感到舒适，它们都是排序好的，需要返回这两个数组的中位数。这具有对数时间复杂度。

之后，我尝试将其推广到找到两个排序数组中的第k小值。这里是SO上的问题。即使在这里，所给出的解决方案对我来说也不明显。但是，即使我设法说服自己接受此解决方案，我仍然好奇如何解决绝对通用的情况（这就是我的问题）

有人可以向我解释一步一步的解决方案（我认为应该采用对数时间，即O(log(n₁) + log(n₂) ... + log(n_N)，其中n₁，n₂...n_N是n个数组的长度），从更具体的情况开始，逐渐推广至更一般的情况吗？

我知道互联网上有很多关于更具体情况的类似问题，但我还没有找到令人信服和清晰的答案。

这里是SO的一个问题（以及其答案），它涉及5个排序数组并找到组合数组的中位数。答案变得过于复杂，以至于我无法推广它。

甚至对于更具体的情况（如我在帖子中提到的情况），干净的方法也是受欢迎的。

附言：你认为这可以进一步概括为未排序数组的情况吗？

附言2：这不是一道作业题，我只是在为面试做准备。

- Sushant

这个问题更适合发到 StackProgramming 上，我觉得。不过我也无法回答你的问题 :) - Daryl Teo

1

什么是对数时间？我们有两个参数，n和k。我认为你无法比O(n)更快，因为你至少需要查看每个数组一次。 - David Grayson

对数意味着类似于 O(lg(n1) + lg(n2) + lg(n3)...)，其中 n1、n2、n3... 是数组 n1、n2、n3...n 的长度。 - Sushant

10个回答

2

这不能在少于 O(n) 的时间内完成。证明草图：如果可以，它必须完全不查看至少一个数组。显然，一个数组可以任意更改第 k 个元素的值。

我有一个相对简单的 O(n*log(n)*log(m))，其中 m 是最长数组的长度。我确信可能会稍微快一些，但不会快很多。

考虑一个简单的情况，你有 n 个长度为 1 的数组。显然，这相当于在长度为 n 的未排序列表中找到第 k 个元素。可以在 O(n) 中找到此元素，参见 Median of Medians algorithm, originally by Blum, Floyd, Pratt, Rivest and Tarjan，并且没有（渐近）更快的算法。

现在的问题是如何将其扩展到更长的排序数组。以下是算法：找到每个数组的中位数。对元组列表（中位数，数组长度/2）进行排序，并按中位数排序。通过保持长度总和来遍历，直到达到大于k的总和。现在您有一对中位数，这样您就知道第k个元素在它们之间。现在对于每个中位数，我们知道第k个元素是大于还是小于它，因此我们可以丢弃每个数组的一半。重复。一旦所有数组都只有一个元素（或更少），我们使用选择算法。

实施这将揭示额外的复杂性和边缘条件，但没有增加渐近复杂度。每个步骤：

1. 找到数组的中位数，每个O(1)，所以总共O(n) 2. 对中位数进行排序，O(n log n) 3. 遍历已排序的列表，O(n) 4. 切片数组，每个O(1)，所以总共O(n)

这是“O(n) + O(n log n) + O(n) + O(n) = O(n log n)” 的表达式。我们必须执行此操作，直到最长的数组长度为1，这需要进行“log m”步骤，总共需要“O(n*log(n)*log(m))”。

你问是否可以将此推广到未排序的数组的情况。不幸的是，答案是否定的。考虑只有一个数组的情况，那么最好的算法将必须至少与每个元素比较一次，总共需要O(m)。如果存在更快的解决方案来处理n个未排序的数组，那么我们可以通过将单个数组分成n个部分来实现选择。由于我们刚刚证明了选择是O(m)，所以我们陷入了困境。

- Philip JF

这只是一个特定的情况，其中k = n/2，即找到中位数等价于找到总体上第n/2小的数。这个特定问题可以通过找到每个数组的中位数来解决（因为数组已经排序，所以时间复杂度为O(1)）。然后，在O(n)时间内找到这n个中位数的最小值和最大值。现在，组合中位数将位于最小和最大中位数之间，因此我们可以摆脱其他元素。这本质上是O(log(maxM))，但我不确定。在您的情况下，对中位数进行排序会使复杂度略微增加，而我们所需要的只是最小值和最大值。 +1 的努力值得肯定。 - Sushant

从求中位数到求第k个数并不难。只选择最小值和最大值的问题在于你不知道抛弃了多少个值，除非我漏掉了什么。排序步骤可以让你扔掉一半的值。但如果能达到O(n*log m)就更好了。 - Philip JF

请注意，我的解决方案与您链接的解决方案具有相同的渐进行为。因为在那种情况下，“ n = 5 ”被视为大O计算中的常数。 - Philip JF

有了中位数在最小值和最大值之间的知识，您可以将与最小中位数对应的数组的下半部分丢弃，将上半部分丢弃到最大中位数。 - Sushant

这个方案如何轻松扩展以找到第k个？ - Sushant

1

存在一种广义方法可以在O(N log k)时间内解决该问题，请参见这里的问题。

- Chao Xu

1

您可以查看我在相关问题这里上的最近回答。相同的思路可以推广到多个数组而不是两个。在每次迭代中，如果k小于所有数组中间索引的总和，则可以拒绝具有最大中间元素的数组的第二半部分。或者，如果k大于所有数组中间索引的总和，则可以拒绝具有最小中间元素的数组的第一半部分，并调整k。重复此过程，直到除一个数组外的所有数组长度都减少为0。答案是最后一个未被剥离为0元素的数组的第k个元素。

运行时间分析：

在每次迭代中，您会消除一个数组的一半。但是要确定哪个数组将被减少，您需要花费与数组数量成线性关系的时间。假设每个数组的长度相同，则运行时间将为cclog(n)，其中c是数组的数量，n是每个数组的长度。

- lambdapilgrim

1

这是代码。O(k*log(m))

public int findKSmallest(int[][] A, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(x -> A[x[0]][x[1]]));
        for (int i = 0; i < A.length; i++)
            queue.offer(new int[] { i, 0 });

        int ans = 0;
        while (!queue.isEmpty() && --k >= 0) {
            int[] el = queue.poll();
            ans = A[el[0]][el[1]];
            if (el[1] < A[el[0]].length - 1) {
                el[1]++;
                queue.offer(el);
            }
        }

        return ans;
    }

- Leandro

1

虽然这是一个旧问题，但是没有一个答案足够好。因此，我将使用 滑动窗口技术 和堆来提供解决方案：

class Node {

    int elementIndex;
    int arrayIndex;

    public Node(int elementIndex, int arrayIndex) {
        super();
        this.elementIndex = elementIndex;
        this.arrayIndex = arrayIndex;
    }

}

public class KthSmallestInMSortedArrays {

    public int findKthSmallest(List<Integer[]> lists, int k) {

        int ans = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> {
            return lists.get(a.arrayIndex)[a.elementIndex] -
                   lists.get(b.arrayIndex)[b.elementIndex];
        });

        for (int i = 0; i < lists.size(); i++) {
            Integer[] arr = lists.get(i);
            if (arr != null) {
                Node n = new Node(0, i);
                pq.add(n);
            }
        }

        int count = 0;

        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            ans = lists.get(curr.arrayIndex)[curr.elementIndex];
            if (++count == k) {
                break;
            }

            curr.elementIndex++;
            pq.offer(curr);
        }

        return ans;
    }
}

这里需要访问的元素数量最大为O(K)，且有M个数组。因此，有效的时间复杂度将是O(K*log(M))。

- Pritam Banerjee

我认为上面的代码有一个错误。在增加和提供之前，您需要添加一个if语句，如下所示：if (curr.elementIndex < arrs[curr.arrayIndex].length - 1) { curr.elementIndex++; pq.offer(curr); } - Leandro

0

如果k不是非常大，我们可以维护一个优先级最小队列。然后循环每个已排序数组的头部以获取最小元素并入队。当队列大小为k时，我们得到了前k个最小值。

也许我们可以将n个已排序数组视为桶，然后尝试使用桶排序方法。

- hxc

复杂度是什么？除了使用O(k)的空间外，您将至少执行K个入队操作，这是O(k log(k))。所以，如果K很大，我们就有问题了。我同意当您需要所有k个最小数字时，这可能是一个好的解决方案，但在这种情况下，我只需要第k个最小值。 - Sushant

0

这可以被认为是归并排序的后半部分。我们可以将所有排序好的列表简单地合并成一个列表...但每次合并只保留k个元素在组合列表中。这样做的优点是仅使用O(k)的空间，但比归并排序的O(n log n)复杂度稍微好一些。也就是说，它在实践中应该比归并排序运行得稍微快一些。从最终组合列表中选择第k小的元素是O(1)。这种复杂度并不算太糟糕。

- Andy

1

是的，这是解决问题的一种简单方案，但不幸的是它不够优化。 - Sushant

0

可以通过在每个数组中执行二分查找并计算较小元素数量来实现。

我使用了 bisect_left 和 bisect_right ，以便使其对非唯一数字也能够工作。

from bisect import bisect_left
from bisect import bisect_right

def kthOfPiles(givenPiles, k, count):
    '''
    Perform binary search for kth element in  multiple sorted list

    parameters
    ==========
    givenPiles  are list of sorted list
    count   is the total number of
    k       is the target index in range [0..count-1]
    '''
    begins = [0 for pile in givenPiles]
    ends = [len(pile) for pile in givenPiles]
    #print('finding k=', k, 'count=', count)
    
    for pileidx,pivotpile in enumerate(givenPiles):
        
        while begins[pileidx] < ends[pileidx]:
            mid = (begins[pileidx]+ends[pileidx])>>1
            midval = pivotpile[mid]
            
            smaller_count = 0
            smaller_right_count = 0
            for pile in givenPiles:
                smaller_count += bisect_left(pile,midval)
                smaller_right_count += bisect_right(pile,midval)
                
            #print('check midval', midval,smaller_count,k,smaller_right_count)
            if smaller_count <= k and k < smaller_right_count:
                return midval
            elif smaller_count > k:
                ends[pileidx] = mid
            else:
                begins[pileidx] = mid+1
            
    return -1

- KRoy

-1

请查看以下C#代码，以查找两个已排序数组联合中的第k小元素。时间复杂度：O（logk）。

public int findKthElement(int k, int[] array1, int start1, int end1, int[] array2, int start2, int end2)
    {
        // if (k>m+n) exception
        if (k == 0)
        {
            return Math.Min(array1[start1], array2[start2]);
        }
        if (start1 == end1)
        {
            return array2[k];
        }
        if (start2 == end2)
        {
            return array1[k];
        }
        int mid = k / 2;
        int sub1 = Math.Min(mid, end1 - start1);
        int sub2 = Math.Min(mid, end2 - start2);
        if (array1[start1 + sub1] < array2[start2 + sub2])
        {
            return findKthElement(k - mid, array1, start1 + sub1, end1, array2, start2, end2);
        }
        else
        {
            return findKthElement(k - mid, array1, start1, end1, array2, start2 + sub2, end2);
        }
    }

- Piyush Patel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michael · Accepted Answer

这种方法不能泛化链接，但可以解决问题：

遍历所有数组，如果有任何一个长度 > k，则将其截断为长度 k（这很傻，但我们稍后会处理 k，所以必须这样做）。
确定最大的剩余数组 A。如果不止一个，请选择一个。
选择最大数组 A 的中间元素 M。
在其余数组上使用二分查找来查找相同的元素（或最大元素 <= M）。
根据各元素的索引计算小于等于 M 和大于 M 的总元素数。这应该给你两个数字：L，小于等于 M 的数量和 G，大于 M 的数量。
如果 k < L，则在找到的分割点处截断所有数组，并在较小的数组上进行迭代（使用下半部分）。
如果 k > L，则在找到的分割点处截断所有数组，并在较小的数组上进行迭代（使用上半部分），并搜索元素（k-L）。

当每个数组只剩下一个元素（或0个元素）时，创建一个大小为 n 的新数组，对其进行排序，并选择第 k 个元素。

因为您始终保证要去掉至少一半的数组元素，因此在 N 次迭代中，您将去掉一半的元素。这意味着有 N log k 次迭代。每次迭代的顺序为 N log k（由于二分查找），因此整个过程是 N^2 (log k)^2。当然，这都是最坏情况，基于只去掉最大数组的一半，而不是其他数组。在实践中，我想典型性能会比最坏情况好得多。