如何判断堆中第k大元素是否大于x
考虑一个包含 n 的二叉堆 数字(根存储最大的数字)。你被赋予了一个 正整数 k < n 和数字 x。你必须确定是否 堆中第 k 大的元素是否大于 x。你的 算法必须花费 O(k) 时间。您可以使用 O(k) 额外存储空间
Consider a binary heap containing n
numbers (the root stores the greatest number). You are given a
positive integer k < n and a number x. You have to determine whether
the kth largest element of the heap is greater than x or not. Your
algorithm must take O(k) time. You may use O(k) extra storage
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
}
}
简单的 dfs 就可以完成这项工作。我们有一个计数器设置为零。从根开始,每次迭代检查当前节点的值;如果大于x,则增加计数器并继续对子节点之一进行算法。如果 counter 大于等于 k 或者没有剩余节点可供检查,则算法终止。运行时间为 O(k),因为最多迭代 k 个节点,并且每次迭代的时间复杂度为 O(1)。
伪代码如下所示。
使用它:
如果node.value < x 则所有子值都小于 x,无需检查。
正如 @Eric Mickelsen 在评论中提到的,最坏情况运行时间恰好是 2k-1 (k>0),如下所示。
Simple dfs can do the job. We have a counter set to zero. Start from the root and in each iteration check the value of current node; if it is greater than x, then increase the counter and continue the algorithm for one of the child nodes. The algorithm terminates if counter is bigger than equal k or if there is no node left to check. The running time is O(k) because at most k node will be iterated and each iteration is in O(1).
A pseudo-code looks like as follows.
use it:
if node.value < x then all children values are smaller than x and there is no need to check.
As @Eric Mickelsen mentioned in comments worst case running time is exactly 2k-1 (k>0) as follows.