我想提出一些方法来解决以下问题:
给定表示为数组的max-heap,返回第k个最大元素而不修改堆.我被要求在线性时间内完成,但被告知可以在日志时间内完成.
我想到了一个解决方案:
使用第二个最大堆并将其填入k或k + 1值(宽度优先遍历到原始值)然后弹出k个元素并获得所需的值.我想这应该是O(N + logN)= O(N)
是否有更好的解决方案,也许是在O(logN)时间？
algorithm heap pseudocode data-structures
algorithm ×1
data-structures ×1
heap ×1
pseudocode ×1