首页 > 试题广场 >

有 n 个无序整数（ n10000）， 则找出其中最大的

[问答题]

有 n 个无序整数（ n>10000）， 则找出其中最大的 M 个数字（ 5<M<10）， 所需要的最小时间复杂度为： ________.

添加回答
zhr4头像 zhr4
  • NLOG(m)
发表于 2017-08-21 16:04:59 回复(2)
啊啊啊62头像 啊啊啊62
O(N)
可以修改数组情况，类似快速排序

O(NlogM)

首先将前M个数存入数组，然后后面M+1...N的数，都比较已有的M个数的最小的数，如果比最小数大，则替换

具体解析：剑指offer
发表于 2017-08-22 12:29:39 回复(0)
孙强Jimmy头像 孙强Jimmy
将n个整数排成大根堆，取堆顶，然后再处理成大根堆，重复M次，时间复杂度为O(MlogN)。
发表于 2017-08-21 09:21:02 回复(2)
Mike-kuang头像 Mike-kuang
O(n) 每次只找一半的快排，参见剑指offer或算导中位数章节
发表于 2018-04-03 19:25:11 回复(0)
Frey1头像 Frey1
nlogn   
发表于 2017-08-18 18:50:14 回复(0)
摩登大西瓜头像 摩登大西瓜
先排序可得复杂度O(logn)，依次取得最后m个数复杂度O(1),最终O(logn)+O(1)=O(logn)
发表于 2017-07-29 15:52:06 回复(3)
范迪康头像 范迪康
nlog2n
发表于 2020-08-31 14:00:50 回复(0)
JohnnyMan头像 JohnnyMan
NlogM，其他都在扯淡
发表于 2017-08-22 13:36:29 回复(0)
starfishYin头像 starfishYin
nlogM
发表于 2017-08-21 22:43:15 回复(0)
自助者天助之头像 自助者天助之
nlogM
发表于 2017-08-19 14:46:49 回复(0)
樵星头像 樵星
mn
发表于 2017-07-11 19:12:06 回复(4)
提交观点

问题信息

复杂度
来自：58同城2017秋招研...
上传者：Cynthiac
难度：
11条回答 3742浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号