在不存储整个数组的情况下单遍查找第 K 大数

Question

我想到的算法是

• 保留大小为 K 的 MaxHeap，
• 如果堆已满，则插入每个元素，
• 删除较小的值。
• 最后，Kth max 是 MaxHeap 的较小者，

这将给我 O(NlogK)。有更好的算法吗？我无法进行快速选择，因为数组无法存储在内存中。

Answer 1

根据您的内存限制，您可以使用中位数算法的修改版本来解决 O(n) 时间和 O(k) 空间中的问题。

想法如下。在内存中维护一个大小为2k的数组。使用数组中的前 2k 个元素填充此缓冲区，然后对其运行中位数算法，将最大的 k 个元素放入数组的前半部分，将最小的 k 个元素放入数组的后半部分。然后，丢弃最小的 k 个元素。现在，将接下来的 k 个元素加载到数组的后半部分，使用中位数算法再次将顶部 k 个元素放在左侧，将底部 k 个元素放在右侧。如果您在数组中迭代此过程 - 将缓冲区的后半部分替换为数组中的下一个 k 元素，然后使用中位数中位数将其中的前 k 个元素移动到左半部分 - 那么最后您将前 k 个元素位于数组的左半部分。找到其中最小的一个（在 O(k) 时间内）将给出第 k 个最大的元素。

总体而言，您最终会使用大小为 O(k) 的数组对中位数中位数算法进行 O(n / k) 次调用，即对需要 O(k) 时间的算法进行 O(n / k) 次调用，净运行时间为 O(n)。这与最后一步相结合，运行时间为 O(n + k) = O(n)。此外，由于中位数步骤的内存使用量为 O(k)，并且由于周围有一个大小为 O(k) 的缓冲区，因此仅使用 O(k) 内存。换句话说，它比最小堆解决方案渐近更快，并且在内存中渐近等效。

希望这有帮助！

Answer 2

这被称为 http://en.wikipedia.org/wiki/Selection_algorithm

中的一种算法特别是 http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

这是 O(N) 时间和 O(1)< /代码> 空间。我相信如果你的数组没有排序，它可以就地完成。如果您的阵列存储在外部（硬盘、网络等），您可以利用必须使用的 ~K 字。如果您的数组是由函数动态生成的，您将遇到类似的情况。

Answer 3

稍微修改算法，因为 maxheap 不支持高效的“查找最小”。

• 将前 K 个项目插入
  min-heap

• 对于剩余的项，如果值大于堆
  头

  • 弹出头部，然后插入新项目。

• 头部是第 K 大的项目。

对于输入，最坏的情况仍然是 O(N lg K)，其中每个项目都大于最后 K 中的最小值。但是对于随机分布的输入，您只需对较小百分比的输入进行堆操作。项目。

Answer 4

运行此代码 - 它运行良好，无需触及元素位置或对其进行排序。

public class nth {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        calc.getit(2);
    }

}
class calc{
    static int arr[] = { 1, 23, 47, 81, 92, 87, 52, 48, 56, 66, 65, 76, 71, 85,
        49, 53, 56, 61, 65, 84 };

    static void getit(int k){
        int i,j=0;
        for(i=0;i<arr.length;i++){
            int c=0;
            for(j=0;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    c++;
                }
            }
            if(c==k-1){
                System.out.println(arr[i]);
            }
        }
    }
}

Answer 5

我有一个 PriorityQueue 的实现。尝试一下：

import java.util.PriorityQueue;

public class FindKthLargestElementWithHeap {

    /**
     * We can use a min heap to solve this problem. 
     * The heap stores the top k elements.
     * Whenever the size is greater than k, delete the min.
     * Time complexity is O(nlog(k)).
     * Space complexity is O(k) for storing the top k numbers.
     */
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>(k);
        for(int i: nums){
            q.offer(i);

            if(q.size()>k){
                q.poll();
            }
        }

        return q.peek();
    }

    public static void main(String args[]) {
        int[] nums = {5,8,6,97,12,3,5,6,4,2,3,};
        //Return the second largest number
        System.out.println(findKthLargest(nums,2));
    }

}

有关更多信息，请访问：https:/ /github.com/m-vahidalizadeh/foundations/blob/master/src/data_structs/FindKthLargestElementWithHeap.java。