我正在努力建立使用锦标赛算法在数组中查找第 k 个最小元素的“O”复杂性。
我已经形成了反向树，最小元素位于反向树的根节点。[(n-1)*log n]
现在我们从底部的最小元素开始提升倒置树。
在每个级别找到根元素的索引不会再次成为 O'n' 操作吗？
我将不得不遍历每个级别的数组以通过“n”比较找到最小（根）元素的索引。[n*log n]
有没有更快的方法来设计每个级别的根元素的索引？
问问题
67 次
1 回答
1
您不能简单地向上树，因为最小元素的父级右侧的叶子小于较小元素的祖父级。像这样：9 / 7 / \ 5 8
我相信您的问题的答案可在如何找到 O(n) 中长度为 n 的未排序数组中的第 k 个最大元素？（将最大更改为最小，您将有一个解决方案）。
于 2014-07-05T02:30:56.747 回答