19

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

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

$输入 = [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 是根，那么 6 是它的子节点，并且它的值大于根的值。我可能错了，但是您的想法是什么以及它的实现基于min heap什么？

4

5 回答 5

19

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

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

在min heap中，根具有最小（小于其子）值。

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

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

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

堆中的所有其他元素（准确地说是 k-1 个元素）都将大于k.

于 2015-09-01T05:28:49.717 回答
5

这是在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（最小堆）的大小为 k，因此任何操作都是log k. 在最坏的情况下，所有数字都按ASC排序，复杂度是n*log k，因为对于每个元素，您需要删除堆顶并插入新元素。

于 2015-09-01T05:46:21.950 回答
3

编辑：检查 O(n) 解决方案的这个答案。

您也可以使用PriorityQueue来解决这个问题：

public int findKthLargest(int[] nums, int k) {
        int p = 0;
        int numElements = nums.length;
        // create priority queue where all the elements of nums will be stored
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        // place all the elements of the array to this priority queue
        for (int n : nums){
            pq.add(n);
        }

        // extract the kth largest element
        while (numElements-k+1 > 0){
            p = pq.poll();
            k++;
        }

        return p;
    }

来自 Java文档：

实现说明：此实现为入队和 出队方法（ 、和）提供O(log(n))时间；和 方法的线性时间；检索方法（、 和）的固定时间。offerpollremove()addremove(Object)contains(Object)peekelementsize

for 循环运行n次数，上述算法的复杂度为O(nlogn).

于 2015-09-01T05:24:27.900 回答
0

如果数组/流中的元素数量未知，则基于堆的解决方案是完美的。但是，如果它们是有限的，但您仍然想要线性时间的优化解决方案怎么办。

我们可以使用此处讨论的快速选择。

数组 = [3,6,2,8,9,4,5]

让我们选择枢轴作为第一个元素：

pivot = 3（在第 0 个索引处），

现在对数组进行分区，使所有小于或等于的元素都在左侧，大于 3 的数字在右侧。就像它在快速排序中完成的一样（在我的博客上讨论过）。

所以在第一遍之后 - [2, 3 ,6,8,9,4,5]

枢轴索引为 1（即它是第二低的元素）。现在再次应用相同的过程。

现在选择 6，在上一个枢轴之后的索引处的值 - [2,3,4,5, 6 ,8,9]

所以现在 6 在正确的位置。

继续检查您是否找到了适当的数字（每次迭代中第 k 个最大或第 k 个最小）。如果找到你就完成了，否则继续。

于 2015-09-01T06:20:46.740 回答
0

常量值的一种方法k是使用部分插入排序。

（这假定了不同的值，但也可以很容易地更改为与重复值一起使用）

last_min = -inf
output = []
for i in (0..k)
    min = +inf
    for value in input_array
        if value < min and value > last_min
            min = value
    output[i] = min
print output[k-1]

（这是伪代码，但应该很容易在 Java 中实现）。

总体复杂性是，这意味着当且仅当它是恒定的或已知小于该值O(n*k)时，它才能很好地工作。klog(n)

从好的方面来说，这是一个非常简单的解决方案。不利的一面是，它不如堆解决方案高效

于 2015-09-01T13:55:50.553 回答