首页 > 试题广场 >

在一个元素个数为N的数组里，找到升序排在N5位置的元素的最

[单选题]
在一个元素个数为N的数组里，找到升序排在N/5位置的元素的最优算法时间复杂度是 
  • O(n)
  • O(n log n)
  • O(n (log n)2)
  • O(n 3/2)
添加回答
推荐
wenyanliu头像 wenyanliu
这是一个顺序统计量的问题，在算法导论9.3章中有专门将这个问题，复杂度可以做到O(n)，用基数排序和桶排序是可以做到的。答案选A
编辑于 2016-02-23 15:24:45 回复(12)
美团到店招聘头像 美团到店招聘
题目又没说要考虑空间复杂度！那就基数排序或者计数排序搞一搞，时间复杂度O(n)。
然后数一数，第N/5个数，不就行了噻！

发表于 2017-02-19 16:20:20 回复(6)
峰风头像 峰风
我认为是：利用快排，一开始将数列分为两部分，用时为n，根据n/5然后在左部分或者右部分继续分割，用时n/2，。。。。最后时间总的为n+n/2+n/4+n/8...=O(n)
发表于 2015-08-15 13:12:54 回复(11)
牛客1867604号头像 牛客1867604号
目前解决TOP-K问题最有效的方法是BFPRT算法，最坏时间复杂度为O(n)。
桶排序的实现前提是输入元素的取值范围在一个有限的集合内，题目并没有限定输入数据的取值范围，可以是任意值，因此当待排序列元素是(0,1)之间的随机小数时，桶排序失效。
发表于 2017-10-11 09:41:11 回复(1)
胡萝卜须头像 胡萝卜须
快排，第一次将数组分为两部分后如果那个关键数恰好是第N/5个则完毕，不然根据其大小在数组的前一半或者后一半接着查找，自后复杂度为Q(N)
发表于 2015-07-29 22:58:08 回复(7)
阳光下的米雪头像 阳光下的米雪
感觉这个属于topK问题，基本思路有以下几种: 思路1：最基本的思路，将N个数进行完全排序，从中选出排在前K的元素即为所求。有了这个思路，我们可以选择相应的排序算法进行处理，目前来看快速排序，堆排序和归并排序都能达到O(NlogN)的时间复杂度。当然，这样的答案也是无缘offer的。思路2：优先队列可以采用数据池的思想，选择其中前K个数作为数据池，后面的N-K个数与这K个数进行比较，若小于其中的任何一个数，则进行替换。这种思路的算法复杂度是O(N*K)，当答出这种算法时，似乎离offer很近了。有没有算法复杂度更低的方法呢？从思路2可以想到，剩余的N-K个数与前面K个数比较的时候，是顺序比较的，算法复杂度是K。怎么在这方面做文章呢？ 采用的数据结构是堆。思路3：大根堆大根堆维护一个大小为K的数组，目前该大根堆中的元素是排名前K的数，其中根是最大的数。此后，每次从原数组中取一个元素与根进行比较，如小于根的元素，则将根元素替换并进行堆调整（下沉），即保证大根堆中的元素仍然是排名前K的数，且根元素仍然最大；否则不予处理，取下一个数组元素继续该过程。该算法的时间复杂度是O(N*logK)，一般来说企业中都采用该策略处理topK问题，因为该算法不需要一次将原数组中的内容全部加载到内存中，而这正是海量数据处理必然会面临的一个关卡。如果能写出代码，offer基本搞定。还有没有更简单的算法呢？答案是肯定的。思路4：快速排序利用快速排序的分划函数找到分划位置K，则其前面的内容即为所求。该算法是一种非常有效的处理方式，时间复杂度是O(N)（证明可以参考算法导论书籍）。对于能一次加载到内存中的数组，该策略非常优秀。
发表于 2019-04-16 11:58:06 回复(0)
emptyCoder头像 emptyCoder
BFPRT才是正解，其它的都是取巧！
发表于 2017-10-29 17:55:55 回复(0)
在拧螺丝的起司很愉快头像 在拧螺丝的起司很愉快
BFPRT可以在最坏情况下以线性时间求得n个数中的第k个数。
发表于 2015-08-15 09:54:29 回复(0)
听见下雨的声音头像 听见下雨的声音
bfprt能达到O(n)
发表于 2015-08-04 15:05:20 回复(0)
BrainerGao头像 BrainerGao

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分 析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂 度，五位算法作者做了精妙的处理。

算法步骤：

1. 将n个元素每5个一组，分成n/5(上界)组。

2. 取出每一组的中位数，任意排序方法，比如插入排序。

3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。

4. 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。

5. 若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。

终止条件：n=1时，返回的即是i小元素。

发表于 2016-03-06 21:47:56 回复(2)
葬爱家族小鑫鑫头像 葬爱家族小鑫鑫
好吧，这个是我认了。
BFPRT天下第一
发表于 2019-05-04 16:51:26 回复(0)
喵喵喵不存在的头像 喵喵喵不存在的
最骚不过BFPRT
发表于 2017-12-12 07:30:58 回复(0)
技术小咔头像 技术小咔
我觉得是先对数组进行排序，最坏的情况时间复杂度为O(n)，然后取第几个元素一目了然
发表于 2017-09-03 11:13:21 回复(2)
刘大猫头像 刘大猫
堆排序，调整五次就行了吧，5n
发表于 2017-09-02 10:31:49 回复(0)
.牛妹头像 .牛妹
寻找数组中的第K大，可以用快排的思想。
1.如果用随机化的快排partition方法，可以达到期望复杂度O(n)，但是最坏的时间复杂度仍然是O（n^2）
2.存在一种最坏时间复杂度是O（n）的算法，也是利用快排的思想，不过找基准的时候需要一些特殊的处理，
        每次分成5组，取每组的中位数的中位数作为基准，使用这个基准再利用快排的思想，可保证最坏情况下时间复杂度为O（n）

以上是总结，看不懂的自行百度或者参考算法导论。
发表于 2017-07-08 21:17:01 回复(0)
被支配的恐惧头像 被支配的恐惧
利用快排，一开始将数列分为两部分，用时为n，根据n/5然后在左部分或者右部分继续分割，用时n/2，。。。。最后时间总的为n+n/2+n/4+n/8...=O(n)
发表于 2017-04-18 09:55:43 回复(0)
wanlanwalan头像 wanlanwalan
找到一个长度为n的数组中第k大的数的最优化时间复杂度为O(n)。

将长度为k的数组进行partition，要比较的次数为k。在长度为n的数组中查找第k大的数字，最坏情况下要进行n-k次partition，复杂度为n+n-1+n-2+...+n-k=kn+k(k+1)/2=O(n)。

发表于 2017-04-07 11:36:59 回复(0)
BWB头像 BWB
其实这个和找第K小的数是一样的？k=N/5
快排思想：找一个数，分成左右两堆（左小右大），如果左边元素个数m大于K，说明是在左边第K小的数，反之在右边。未选择的那边丢弃，剩下的重复，进行次数为a次。
第K小的数时间复杂度为O(N*loga)≈O(N)，而快排为O（N*logN）原因是没有丢弃任何一边。
发表于 2017-03-02 21:03:35 回复(1)
乱矢头像 乱矢
逐次比较，大于自己有5个的为正确
发表于 2016-08-19 00:05:37 回复(0)
abcde666666头像 abcde666666
用快排，每次只要将基准元素和N/5进行比较，然后要么在左边要么在右边，不需要两边都递归，减少了快排的复杂度。
比如第一次没找到的时间复杂度O(n),第二次没找到的时间复杂度O(n/2)....第K次找到O(1/2^k)
总得时间复杂度=O(n(1+1/2+....1/2^k))=O（n）
发表于 2016-04-13 15:10:15 回复(0)
星痕sky头像 星痕sky
快去排序需要经过至少一趟排序才知道关键字在第几个位置，一趟排序时间复杂度为n，如果正好为n/5，则完成。
发表于 2016-01-09 16:29:09 回复(0)
提交观点

问题信息

数组 复杂度 阿里巴巴 排序
来自：网易内推笔试练习卷
上传者：享受孤独
难度：
32条回答 23978浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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