0

所以我实现了我自己的第 k 阶统计搜索来查找未排序数组中的第 k 个最大元素。但是我刚刚意识到我使用的算法（可以在这里找到：http: //pine.cs.yale.edu/pinewiki/QuickSelect）返回元素本身，但是我实际上想返回第 k 个最大的索引元素。有没有办法做到这一点？

4

1 回答 1

2

使用 QuickSelect 返回第 k 个统计量的原始索引是不可行的。该算法是就地的，它会打乱数组。您必须在开始时制作原始数组的副本（或在元素移动时跟踪元素，这也需要 O(n) 内存并且要复杂得多。）

于 2012-12-17T21:38:31.437 回答