Java,从数组中查找Kth最大值

Question

我接受了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);
}

我刚刚测试过,该方法可以根据问题正常工作.然而,受访者说,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 heap.根据我的知识,堆的每个子值不应超过根值.因此,在这种情况下,如果我们假设3是root,那么6是它的子节点,它的值比root的值更大.我可能错了,但您的想法是什么,它的实现基于min heap什么？

Answer 1

他实际上给了你整个答案.不只是一个提示.

而你的理解是基于max heap.没有min heap.它的工作原理是不言自明的.

在最小堆中,根具有最小值(小于它的子节点)值.

所以,你需要的是,迭代数组并K在min heap中填充元素.一旦完成,堆就会自动包含根目录中的最低值.

现在,对于从数组中读取的每个(下一个)元素, - >检查该值是否大于最小堆的根. - >如果是,请从min heap中删除root,然后将值添加到它.

遍历整个数组后,min heap的根将自动包含第kth个最大元素.

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

Answer 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).PriorityQueue(Min Heap)的大小为k,因此任何操作都是log k.在最坏的情况下,其中所有数字都按ASC排序,复杂性是n*log k,因为对于每个元素,您需要删除堆顶部并插入新元素.