n个数值选出最大m个数（3mn）的最小算法复杂度是_

牛客455819号

额，为什么不可以用哈希表？我选的是O(n)…………

发表于 2016-07-09 09:12:18 回复(0)

牛客1481368号

为什么不可以建一个大小为n的堆，取前m个数啊，复杂度不就是D选项了吗 D选项复杂度比E还要低啊

发表于 2016-09-08 16:36:06 回复(0)

granet

剑指offer第30题

1.最简单的方法：将n个数排序，排序后的前k个数就是最大的k个数，这种算法的复杂度是O（nlogn）

2.O（n）的方法：利用快排的patition思想，基于数组的第k个数来调整，将比第k个数小的都位于数组的左边，比第k个数大的都调整到数组的右边，这样调整后，位于数组右边的k个数最大的k个数(这k个数不一定是排好序的）

3.O(nlogk）的方法：先创建一个大小为k的最小堆，接下来我们每次从输入的n个整数中读入一个数，如果这个数比最小堆的堆顶元素还要大，那么替换这个最小堆的堆顶并调整。

编辑于 2016-12-14 17:57:46 回复(37)

lucenya

n是因为需要访问一遍n个数 logm是因为需要将m个数排序，排序后才能进行对比

发表于 2016-05-14 14:51:57 回复(0)

月生烟

BFPRT ( 线性查找算法 )找出第m个大的值，该步的时间复杂度为O(n)，然后在遍历数组选出大于等于m的值，该步的时间复杂度为O(n)，总的时间复杂度为O(2n)=O(n)

编辑于 2016-08-27 22:57:24 回复(3)

selfboot

答案是错误的吧，用 partition 来做的话可以 O(N) 的

发表于 2016-05-06 14:11:28 回复(5)

hehehe1

维持一个大小为m的数组，建立极小堆，时间复杂度为logm,然后遍历剩下的n-m个元素，若大于堆中最小值，则替换，替换完了进行堆调整。这样复杂度为nlogm。

发表于 2016-05-19 17:11:40 回复(5)

Echo001

使用堆排序，任选m个数建立小顶堆，遍历另外的n-m个数，如果遇到的元素比堆顶元素小，则忽略；如果遇到的数比堆顶元素大，则替换堆顶元素，并调整堆为小顶堆，调整堆的时间复杂度为O(logm),遍历另外的n-m个数的时间复杂度为O(n-m)，即为O(n)，最坏情况下，对遇到的每一个数都要调整堆，则时间复杂度为O(nlogm)。

如果说最小时间复杂度就是，选择的前m个数是从大到小有序的，并且是最大的m个数，只需要调整一次堆O(logm)，以后对剩下的数遍历时不需要调整堆，则时间复杂度为O(n)，即只考虑遍历的情况。

编辑于 2016-07-23 15:41:23 回复(0)

huixieqingchun

O(nlogk）的方法：先创建一个大小为k的最小堆，接下来我们每次从输入的n个整数中读入一个数，如果这个数比最小堆的堆顶元素还要大，那么替换这个最小堆的堆顶并调整。

发表于 2016-09-08 15:43:25 回复(0)

LittleBaby

本题答案错误，应该选A。

从n个数中选出第m大的数，最低时间复杂度为O(n)，利用的是快速排序的划分思想。那么，从n个数中选处最大m个数，其复杂度应该跟前者是一样的。另可参加《剑指offer》第30个面试题。

发表于 2016-09-03 22:34:59 回复(2)

asyoguo

【算法基本描述】一遍扫描+最小堆
【算法伪代码】
00-建立一个最小堆（优先队列）,最小堆的大小控制在m之内
01-for 每个数：
02-----if 这个数比最小堆的堆顶元素大：
03---------弹出最小堆的最小元素
04---------把这个数插入到最小堆
05-最小堆中的m个元素就是所要求的元素
06-其中最小堆的作用就是保持里面始终有m个最大元素,且m个元素中最小的元素在堆顶.

发表于 2016-05-16 10:55:49 回复(1)

六纛鼓

题目只问最小复杂度，首先遍历n个数，求出最大数max, 然后建立一个max大小的数组，初始化值为0，然后，便利n个数，存在的max数组中置为1，最后，从后向前面便利max数组，输出前m个数。一共三趟便利，每次都是O(n),所以复杂度为O(n).

发表于 2019-03-05 20:52:26 回复(1)

荒漠

获取前m个最大数，应该是先排序后获取，而排序中最快的时间复杂度就计数排序 O(n)

发表于 2018-11-18 11:36:57 回复(0)

FunkyARUI

只有我是通过计数排序得到A的吗？不过不知道这里能不能用计数排序。快排的最坏情况确实不是O(n)，不过一般是说平均的话可以达到O(n)。

发表于 2017-03-03 10:43:28 回复(2)

陕西大水牛

做错了，真讨厌。

n的话是直接遍历。

mlogn是红黑树

nlogm是保存数组为一个堆，然后每次跟堆顶判，小插入，插入为logm，大则比较下一个。

发表于 2016-08-18 14:36:15 回复(1)

弹指江山

1.最简单的方法：将n个数排序，排序后的前k个数就是最大的k个数，这种算法的复杂度是O（nlogn）

2.O（n）的方法：利用快排的patition思想，基于数组的第k个数来调整，将比第k个数小的都位于数组的左边，比第k个数大的都调整到数组的右边，这样调整后，位于数组右边的k个数最大的k个数(这k个数不一定是排好序的）

3.O(nlogk）的方法：先创建一个大小为k的最小堆，接下来我们每次从输入的n个整数中读入一个数，如果这个数比最小堆的堆顶元素还要大，那么替换这个最小堆的堆顶并调整。

发表于 2016-08-09 15:25:54 回复(3)

Strawberryflavor

这答案就是a好吧，计数排序算法复杂度最坏也是O（n）,排好序结果就出来了

发表于 2020-03-20 15:46:21 回复(0)

天遥201906261523858

取第一个数暂时当做最大数，变量m此时等于0，逐个比较，有比他大的，覆盖数值并且将m归零，相等的，m+1，最终结果+1，就是m的实际值，所以结果是n

发表于 2024-03-08 06:23:52 回复(0)

起了一个响亮名字的牛百万

要解决这个问题，我们可以使用一个称为"选择算法"的方法。选择算法可以帮助我们在一个未排序的数值列表中找到最大的m个数。以下是解决这个问题的步骤：首先，我们需要确保你有一个包含n个数值的列表。假设这个列表是一个数组，命名为numbers。创建一个变量m，用于存储你想选择的最大数的数量。我们将使用一个循环来进行选择排序。循环从0到n-m-1，每次迭代都会选择当前未排序部分的最大数，并将其放在已排序部分的末尾。在每次迭代中，我们需要找到当前未排序部分的最大数。我们可以使用一个变量maxIndex来记录当前最大数的索引位置。初始时，将maxIndex设置为0。接下来，我们需要遍历当前未排序部分的数值，从索引位置1到n-m-1。在每次迭代中，我们将比较当前数值与当前最大数的大小。如果当前数值大于当前最大数，我们将更新maxIndex为当前数值的索引位置。在遍历完当前未排序部分的数值后，我们将交换maxIndex和当前未排序部分的最后一个数值。这样，当前未排序部分的最大数就会被放置在已排序部分的末尾。重复步骤3到步骤6，直到已排序部分包含了m个最大数。这个选择算法的平均时间复杂度为O(n*m)，其中n是数值列表的长度，m是要选择的最大数的数量。请注意，这个算法在每次迭代中只选择一个最大数，所以它的复杂度是线性的。

发表于 2023-10-20 18:18:07 回复(0)

辉小歌

遍历一下即可。开一个小根堆。堆的个数小于m直接进堆，否则的话和堆顶比较。大于的话替换堆顶。最后堆内元素就是最大的m个数。

发表于 2022-10-06 14:40:04 回复(1)

n个数值选出最大m个数（3mn）的最小算法复杂度是

问题信息

热门推荐

相关试题