这是一个家庭作业问题,所以我想避免完整的答案,如果可能的话,更喜欢提示.
给定一个随机整数数组A [1 ... x],程序应按递增顺序返回前y个数组元素,其中1 <= y <= sqrt(x).所以,基本上,给定一个数组[5,9,2,8]和y = 2,程序应返回[2,5].
"排序第一,返回前y项"答案在窗外,因为我们能做的最好的是n*logn time with merge或quicksort.答案因此必须利用我们只返回最多sqrt(x)项的事实,而我到目前为止唯一的另一个答案是对数组中的最小元素进行for循环搜索,从中删除最小值数组,将它存储在一个新的数组中,比如B,并在现在较小的修改版本的A长度x-1上重复该过程,这给我们这样的运行时间:
x + (x-1) + (x-2) + ... + (x-y)
这计算了min-search的for循环迭代次数,并且在最坏的情况下给出了最多y或sqrt(x)次迭代,并且数组中最多有x个项.所以我们有sqrt(x)*x,它比O(n*logn)好,但仍然不是O(n):/.
小智 9
提示:假设你有一个O(n)时间算法来挑选第y 个元素......