我要招人

去企业版

首页 > 试题广场 >

在N个乱序数字中查找第k大的数字，时间复杂度可以减小至

[单选题]

在N个乱序数字中查找第k大的数字，最优时间复杂度可以为

```
O(N*logN)
```
```
O(N)
```
```
O(1)
```
```
O(N^2)
```

查看答案及解析

gulu

用快排partiton只能说是接近O（n）吧

发表于 2015-08-22 17:49:40 回复(0)

Amy_sh

A。大牛们有更好的方法，还请分享~

发表于 2014-10-14 15:46:14 回复(0)

seekerjie

基于数组的第n-k个数字来调整，按照快排Partion思路排序

编辑于 2015-08-08 10:59:36 回复(0)

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:41:37 回复(1)

百度高级测试开发工程师

答案解析：解法1：我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。

解法2：利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)

解法3：利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；

2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)

解法4：二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)

解法5：用O(4*n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn)

解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)

解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

发表于 2016-01-17 00:16:43 回复(13)

lwya

这是一个顺序统计量问题，在算法导论9.3章有讲到，用基数排序和桶排序均可做到O(n)

发表于 2015-07-24 10:56:12 回复(9)

Gason

B。顺序统计问题，按照快速排序Partion思路，复杂度O(N)。

发表于 2015-07-23 09:06:44 回复(12)

奋斗的小鸟

利用快排的partion思想

T(n) = 2T(n/2) + O(1)

时间复杂度O(n)

编辑于 2015-08-11 23:10:28 回复(0)

Goats

不用全部排序，故复杂度降低，仅取K大，桶排序

发表于 2016-04-10 16:54:40 回复(0)

牛客830030224号

快排不是o(nlogn)？

发表于 2022-11-02 14:22:15 回复(0)

学术废物

考虑以空间换时间

发表于 2022-03-18 23:02:07 回复(0)

黏黏糖

利用hash保存数组中元素S[i]出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

发表于 2017-06-19 20:15:17 回复(0)

LeoEatle

用选择排序遍历k遍不就行了

时间复杂度是O(k*N)

发表于 2016-08-02 15:58:39 回复(0)

菩提旭光

答案：B

实现思路：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

发表于 2015-08-22 16:39:57 回复(0)

Double_k

bfptr算法，左大神有讲过

发表于 2015-08-22 13:36:30 回复(0)

飞鸟

我觉得使用空间换时间，用大小为N+1的数组，遍历一边数组，然后在相应位置+1，遍历一边时间复杂度为O（n）;后面的就是找到第K个大的数就行了。

发表于 2015-08-14 09:28:46 回复(0)

sam_zhu

用求轴点的方法，看前后分割的数组下标，找到第k的位置，然后将其他值与k位置的值比较，若值比k大不动，比k小扔前面，这样比较n次就能找到

发表于 2015-08-10 18:28:17 回复(2)

亦珍

用bfprt算法可以实现时间复杂度0（N）

发表于 2015-08-09 21:31:28 回复(0)

superzhang

堆排序时间负责度NlgK

发表于 2015-08-02 12:51:32 回复(0)

提交观点

问题信息

复杂度阿里巴巴

来自：阿里巴巴2015实习生笔试题

上传者：水深35米

难度：

19条回答 1333收藏 41527浏览

在N个乱序数字中查找第k大的数字，时间复杂度可以减小至

问题信息

热门推荐

相关试题