在不存储整个数组的情况下，在单次遍历中找到第K大的数

Question

在不存储整个数组的情况下，在单次遍历中找到第K大的数

arraysalgorithmselectionspace-complexity

5

我所想的算法是：

维护一个大小为K的最大堆
插入每个元素
如果堆已满，则删除较小的值
最后，第K大的元素就是最大堆中的最小值

这将给出O(NlogK)的时间复杂度。是否有更好的算法？我不能使用快速选择，因为数组无法存储在内存中。

- Wei Shi

2

@Henk Holterman：要求不能将数组存储在内存中，这使得它不是那个答案的重复。 - btilly

5个回答

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个单词。如果您的数组是由函数动态生成的，则会面临类似的情况。

- ninjagecko

1

它的辅助空间复杂度为O(1) - 你仍然需要存储原始数组，而原帖中说他无法这样做。 - IVlad

@|/|ad：我知道；OP说他不能把全部存储在内存中。他仍然必须将其存储在某个地方（除非它是动态生成的）。如果他正在使用内存，则如果他的数组未排序，可以就地执行操作。如果他使用其他存储，那就没有问题。此外，他显然正在使用~`K`个字的内存，如果他愿意，他可以使用这些内存进行操作。 - ninjagecko

0

我有一个使用优先队列实现的代码。你可以试试看：

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。

- Mohammad

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]);
            }
        }
    }
}

- TukS57

0

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

将前K项插入最小堆
对于剩余的项，如果其值大于堆顶
- 弹出堆顶，并插入新项。
堆顶是第K大的项。

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

- AShelly

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

根据您的内存限制，可以使用改进版中位数算法以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)的内存。换句话说，它在渐进意义下比使用最小堆的解决方案更快，并且在内存上是渐进等效的。

希望这可以帮助您！