求取一个数组最大K 个数,返回K个数结果为有序数组。假设数组有N 个元素,要求算法时间复杂度不超过O(N*log(K)) ,空间复杂度为O (1 )。 如: input : [3, 2, 1, 4, 5] 2 output : [4,  5]-笔试面试资料

这是qklbishe.com第9312 篇笔试面试资料
提供答案分析,通过本文《求取一个数组最大K 个数,返回K个数结果为有序数组。假设数组有N 个元素,要求算法时间复杂度不超过O(N*log(K)) ,空间复杂度为O (1 )。 如: input : [3, 2, 1, 4, 5] 2 output : [4,  5]-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

求取一个数组最大K个数,返回K个数结果为有序数组。假设数组有N个元素,要求算法时间复杂度不超过O(N*log(K)),空间复杂度为O1)。
如:
input
[3, 2, 1, 4, 5]
2
output
[4, 5]

求取一个数组最大K 个数,返回K个数结果为有序数组。假设数组有N 个元素,要求算法时间复杂度不超过O(N*log(K)) ,空间复杂度为O (1 )。    如:    input :    [3, 2, 1, 4, 5]      2      output :    [4,  5] 区块链毕设学生260047603号
本来想着直接sort之后从尾部取n个数。但这样时间复杂度至少是O(N log(N))了。
于是想到了下面的算法:
import re import bisect  ls = input() ls = re.sub("[^-0-9,]", "", ls) ls_int = list(map(int, ls.split(',')))  n = int(input()) res = list() for i in ls_int:     # 二分法插入     bisect.insort(res, i)      # 如果res已经有n个数字在里面了     if(len(res)>n):         # 最小的那个被挤掉了         del res[0]           print(res)

空间复杂度O(1)。

时间复杂度:
首先遍历一遍整个list,O(N)
对于每一个元素,进行一次二分法插入(插入长度至多为K的res这个list),所以每一次插入的复杂度是O(log K)。
整个算法就是上面两步的结合,所以时间复杂度O(N log K)

2021-04-11 15:49:35 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 求取一个数组最大K 个数,返回K个数结果为有序数组。假设数组有N 个元素,要求算法时间复杂度不超过O(N*log(K)) ,空间复杂度为O (1 )。 如: input : [3, 2, 1, 4, 5] 2 output : [4,  5]-笔试面试资料

提供最优质的资源集合

立即查看 了解详情