在具有N个元素的整数数组中,找到最小的k个元素？

Question

可能重复:
用于进行k选择的最坏情况O(n)算法

鉴于以下问题:

In an integer array with N elements , find the minimum k elements (k << N)

你可以假设这N是一个很大的数字.

我在考虑最小堆,任何人都有更好的解决方案？

问候

Answer 1

如果K << N,min heap足够好,因为堆的创建是O(n),如果K << N选择前K个项最多是O(N),否则你可以使用选择算法来找到第K个最小元素在O(n)再选择这比找到的项目更小的数字.(当然,如果某些数字等于Kth元素选择直到填充K项目).