在n个数的列表中找出m个最小的数的算法。

问题描述 投票:1回答:2

我要写一个算法来寻找 "n个数列表中的m个最小的数"。我不明白这一行是什么意思。我是否必须在一个列表中找到所有最小的数字并打印出来。比如说我有一个列表,比如说4个元素[10,20,30,40],我是不是要把每一个小于40的数都打印出来,一次迭代一次。还是有什么其他的含义让我摸不着头脑。

algorithm
2个回答
1
投票

他们要求的是:给定一个n个数的列表,找出m个最小的数。所以,如果n=10,m=5,列表是这样的。

 Input: 1 4 2 6 3 6 2 4 6 1
Output: 1 1 2 2 3

解决这个问题的方法是用n个数字的集合中的前m个数字来填充max堆. 然后,再把列表中剩余的n-m个数,与max-heap的最大值进行比较。如果列表中的数字小于max列表的max,则从max列表中删除max,并用列表中的当前数字代替。重复上述操作,直到所有的数字都被检查过,然后返回m堆中的项目。

这样做的复杂度是O(nlogm),因为在取第一个m对max堆进行质化后,你对列表中的(n-m)元素各做一次潜在的删除和一次插入。


1
投票

我的理解是,你必须写一个函数,把一个数字m作为参数,然后返回一个大小为m的数组,其中包含m个最小的数字。以你的例子来说,如果我们说m是2,我们将返回一个2个元素的数组,其中包含2个最小的元素。[10,20] 如果我们将m设为3,函数将返回以下结果 [10,20,30]

© www.soinside.com 2019 - 2024. All rights reserved.