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

arrays algorithm java min-heap

2022-09-02 12:56:33

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

假设您有一个具有 N 个不同值的无序数组

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

实现一个查找第 K 个最大值的函数。

EG：如果 K = 0，则返回 9。如果 K = 1，则返回 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);
}

我刚刚测试过，根据问题，该方法工作正常。然而，受访人说，作为提示，他建议使用。据我所知，堆的每个子值不应超过根值。因此，在这种情况下，如果我们假设3是根，那么6是它的子级，它的值比根的值更粗糙。我可能错了，但你的想法是什么，它的实现基于什么？in order to make your life complex! lets assume that your array contains millions of numbers then your listing becomes too slow. What you do in this case?min heapmin heap

答案 1

他实际上已经给了你整个答案。不仅仅是一个提示。

而您的理解是基于.不。它的运作是不言自明的。max heapmin heap

在最小堆中，根具有最小值（小于其子项）。

因此，您需要的是，循环访问数组并在最小堆中填充元素。完成后，堆会自动包含根目录中的最低值。K

现在，对于从数组中读取的每个（下一个）元素，->检查该值是否大于最小堆的根。-> 如果是，请从最小堆中删除根，并向其添加值。

遍历整个数组后，最小堆的根将自动包含第三大元素。k

堆中的所有其他元素（确切地说是 k-1 元素）将大于。k

答案 2

以下是在java中使用PriorityQueue的Min Heap的实现。复杂度：n * log k。

import java.util.PriorityQueue;

public class LargestK {

  private static Integer largestK(Integer array[], int k) {
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k+1);
    int i = 0;
    while (i<=k) {
      queue.add(array[i]);
      i++;
    }
    for (; i<array.length; i++) {
      Integer value = queue.peek();
      if (array[i] > value) {
        queue.poll();
        queue.add(array[i]);
      }
    }
    return queue.peek();
  }

  public static void main(String[] args) {
    Integer array[] = new Integer[] {3,6,2,8,9,4,5};
    System.out.println(largestK(array, 3));
  }
}

输出：5

代码循环到数组（O（n）上。优先级队列（最小堆）的大小为 k，因此任何操作都将是 log k。在最坏的情况下，所有数字都排序为ASC，复杂度为n*log k，因为对于每个元素，您需要删除堆的顶部并插入新元素。