5

我想到的算法是

  • 保持一个大小为 K 的 MaxHeap
  • 插入每个元素
  • 如果堆已满，则丢弃较小的值
  • 最后，Kth max 是 MaxHeap 中较小的一个

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

4

5 回答 5

11

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

思路如下。在内存中维护一个大小为 2k 的数组。用数组中的前 2k 个元素填充此缓冲区，然后对其运行中位数算法，将最大的 k 个元素放在数组的前半部分，将最小的 k 个元素放在后半部分。然后，丢弃最小的 k 个元素。现在，将接下来的 k 个元素加载到数组的后半部分，使用中位数算法再次将顶部 k 个元素放在左侧，底部 k 个元素放在右侧。如果你在整个数组中迭代这个过程 - 用数组中的下一个 k 元素替换缓冲区的后半部分，然后使用中位数的中位数将这些元素的前 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) 内存。换句话说，它比最小堆解决方案渐近更快，并且在内存中渐近等效。

希望这可以帮助！

于 2011-06-22T21:43:10.530 回答
1

这被称为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必须使用的单词。如果您的数组是由函数动态生成的，您将处于类似的情况。

于 2011-06-22T21:36:23.547 回答
0

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

  • 将前 K 项插入 最小堆

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

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

  • 头部是第 K 个最大的项目。

最坏的情况仍然是 O(N lg K) 对于每个项目大于最后一个 K 的最小的输入。但是对于随机分布的输入，您只需要对较小百分比的项目。

于 2011-06-22T21:39:18.430 回答
0

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

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]);
            }
        }
    }
}
于 2014-04-27T08:56:25.377 回答
0

我有一个使用 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_structures/FindKthLargestElementWithHeap.java 。

于 2016-09-19T20:28:20.550 回答