Java，从数组中查找第 K 个最大值

Question

这个问题在这里已经有了答案:

How to find the kth largest element in an unsorted array of length n in O(n)? (32 个回答)

关闭 7 年前。

我接受了 Facebook 的采访，他们问了我这个问题。

Suppose you have an unordered array with N distinct values

$input = [3,6,2,8,9,4,5]

Implement a function that finds the Kth largest value.

EG: If K = 0, return 9. If K = 1, return 8.

我做的就是这个方法。

private static int getMax(Integer[] input, int k)
{
    List<Integer> list = Arrays.asList(input);
    Set<Integer> set = new TreeSet<Integer>(list);

    list = new ArrayList<Integer>(set);
    int value = (list.size() - 1) - k;

    return list.get(value);
}

我刚刚测试过，该方法根据问题运行良好。但是，受访者说，为了让你的生活复杂!假设您的数组包含数百万个数字，那么您的列表会变得太慢。在这种情况下你会怎么做？作为提示，他建议使用min heap。根据我的知识，堆的每个子值不应超过根值。因此，在这种情况下，如果我们假设 3 是根，那么 6 是它的子节点，并且它的值大于根的值。我可能错了，但是您的想法以及基于 min heap 的实现是什么？

Answer 1

他实际上已经给了你全部的答案。不仅仅是提示。

而你的理解是基于max heap。不是最小堆。它的工作原理是不言自明的。

在最小堆中，根具有最小(小于其子堆)值。

所以，您需要的是遍历数组并在 min heap 中填充 K 元素。一旦完成，堆会自动包含根处的最低值。

现在，对于您从数组中读取的每个 (next) 元素， -> 检查该值是否大于最小堆的根。 -> 如果是，则从最小堆中删除根，并将值添加到其中。

遍历整个数组后，min heap 的根会自动包含第 k 个最大的元素。

堆中的所有其他元素(准确地说是k-1个元素)都将大于k。