logo标签列表

查找第k小的元素的数据结构

algorithmdata-structuresheap
5

我在这里有一个问题，需要设计一种数据结构，对以下三个操作保证最坏情况下的时间复杂度为O(lg n):

  a) Insertion: Insert the key into data structure only if it is not already there.
  b) Deletion: delete the key if it is there!
  c) Find kth smallest : find the ݇k-th smallest key in the data structure

我在考虑是否应该使用堆，但我对此仍没有明确的想法。


我可以很容易地在O(lg n)甚至更快的时间内获得前两部分，但不确定如何处理第c部分。

如果有人有任何想法，请分享。

2
如果您使用堆，您将如何找到最小的元素？然后，您将如何找到第二小的元素？第三、第四、第五小的元素呢？现在，您将如何找到第k小的元素？找到第k小的元素的处理顺序是什么？（提示：它将是O(k lg n)） - abelenky
5个回答
8

有两种解决方案：

  • 使用平衡二叉搜索树（红黑树、AVL树、Splay树等都可以）。你已经熟悉操作（1）和（2）。对于操作（3），只需在每个节点上存储一个额外的值：该子树中节点的总数。您可以轻松使用此值在O(log(n))时间内找到第k小的元素。 例如，假设您的树如下所示——根A有10个节点，左子B有3个节点，右子C有6个节点（3 + 6 + 1 = 10），假设您想要找到第8个最小的元素，您知道应该去右边。

  • 使用跳表。它也支持您所有的（1）、（2）、（3）操作，平均时间复杂度为O(logn)，但可能需要更长的实现时间。

6

如果你的数据结构保持元素排序，那么找到第k小的元素就很容易。

我认为这个答案没有问题（至少目前还没有）；如果你给它点了踩，请考虑留下评论。事实上，这似乎是一个非常合理的答案。 - ninjagecko
+1 实际上，这个答案似乎是基本正确的（除了O(1)）：使用跳表来跟踪元素。执行在线插入排序以保持元素在可索引跳表中排序。插入、删除和索引（第k大的元素）每个操作都是O(log(N))（不过，除非你能找到另一个动态更新的数据结构，否则不是O(1)）。 - ninjagecko
我点赞是因为它所说的是正确且相关的提示。我同意，如果没有在评论中解释原因就进行-1操作似乎有些令人沮丧。 - gbulmer
1

二叉搜索树在最坏情况下的搜索和插入成本是O（N），而平均情况下的成本是O（lgN）。

因此，我建议使用红黑二叉搜索树，它保证了搜索和插入的最坏复杂度为O（lgN）。

您可以在这里阅读有关红黑树的更多信息，并查看Java中Red-Black BST的实现此处。因此，在使用上述Red-Black BST实现查找第k小元素时，只需调用select方法并传递k即可。该select方法还保证了最坏的O（lgN）成本。

1
确实，您可以这样做。我认为您需要用“此元素的子节点数量”来增强二叉树中每个交汇点的元数据，这样您就可以通过从根节点下降树来执行二进制搜索以找到第k个元素。 - ninjagecko
0

使用堆不是找到数组第K小元素的正确结构，因为您必须从堆中删除K-1个元素才能获得第K个元素。

有一种更好的方法来查找第K小元素，它依赖于中位数算法。基本上，任何分区算法平均而言都足够好，但中位数算法具有查找中位数的最坏情况O(N)时间证明。一般来说，此算法可用于查找任何特定元素，而不仅仅是中位数。

这里是在C#中分析和实现此算法的链接：在未排序的数组中查找第K小元素

附带说明，有许多事情可以在数组中原地完成。数组是一种很棒的数据结构，只有在特定情况下知道如何组织其元素时，您才可能获得极快且无需额外内存使用的结果。

堆结构是一个很好的例子，快速排序算法也是如此。这里有一个非常有趣的数组高效使用的例子（这个问题来自编程奥林匹克）：在数组中查找主要元素。
0

其中一种解决方案可以使用快速排序的策略。

步骤1：将第一个元素作为枢轴元素并将其放置在正确的位置。（最多n次检查） 当您到达此元素的正确位置时，进行检查

步骤2.1：如果位置>k 您的元素位于第一个子列表中。因此，您对第二个子列表不感兴趣。

步骤2.2 如果位置

步骤2.3 如果位置== k 您已经获得了该元素，请打破循环/递归

步骤3：通过使用适当的子列表重复步骤1到2.3

此解决方案的复杂度为O（n log n）

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接