在具有N个元素的整数数组中，找到最少k个元素？ [英] In an integer array with N elements , find the minimum k elements?

问题描述

可能重复：

给出以下问题：

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

您可以假定 N 很大。

我在考虑最小堆，有人有更好的解决方案吗？

I'm thinking about a minimum heap , anyone has a better solution ?

问候

推荐答案

如果K<< N，最小堆就足够了，因为堆的创建是O（n），并且如果K ＜ N个选择的前K个项目最多为O（N），否则，您可以使用选择算法来在 O（n）中找到第K个最小元素，然后选择小于找到的项目的数字。 （确保某些数字等于Kth元素，直到填充 K 个项目为止。）。

If K << N, min heap is good enough because creation of heap is O(n), and if K << N selecting first K items is at most O(N), otherwise you could use selection algorithm to find Kth smallest element in O(n) then select numbers which are smaller than found item. (Sure if some numbers are equal to Kth element select till fill K items).

这篇关于在具有N个元素的整数数组中，找到最少k个元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！