首页 > 试题广场 >

一个无序 double 型数组(可以修改内容),长度 n,找

[单选题]
一个无序 double 型数组(可以修改内容),长度 n,找出前 k 个最小值的算法复杂度最低的是:()
  • O(nLog n)
  • O(nLog k)
  • O(n)
  • O(log n)
当k=1,即找出数组的最小值,必须遍历数组所有元素,O(n),排除其他答案,选C。
发表于 2019-08-16 14:23:30 回复(2)
可以考虑桶排序 将double乘以一个足够大的数变成 Long  排序,算法复杂度就是O(n)
编辑于 2020-12-08 11:15:08 回复(0)

类似抽象的变量,让其特殊化即可轻松解题。


发表于 2019-09-10 02:08:36 回复(0)
这个即使用Partition方法,也是平均O(N) 吧。对于特例来说,需要递归N次,每次交换N个。
就像快排最差是O(N2),平均是O(NlogN)一样
发表于 2019-09-08 10:50:49 回复(0)
查找第k小的数,利用快排中的划分Partition()函数,找到第k小的数a[k-1],则a[0...k-1]是前k小的数(无序),为O(n)
发表于 2019-08-20 17:54:17 回复(0)