试题-对n个数字进行排序，期中两两不同的数字的个数为k，n远远大于k，而n的取值区间长度超过了内存的大小，时间复杂度最小可以是?

题目

对n个数字进行排序，期中两两不同的数字的个数为k，n远远大于k，而n的取值区间长度超过了内存的大小，时间复杂度最小可以是?

A.O（nlogk）

B.O（nk）

C.O（n）

D.O（nlogn）

上一题 暂无更多

解答

正确答案是 C

先通过hash来获得这k个数，以及每个数对应的个数，然后对k个数进行排序。复杂度为O(N)，所以选择c

C 10条回复评论

小朱吖

好文，喜欢看，比书上的好

发表于 2023-06-16 22:00:00

0 0

博客园

我是前年在培训班学的平面设计，总的来说只能教你一些最基础的，真正有用的东西都是在实际工作中加上自身空闲时间的摸索来学会的。

发表于 2022-10-29 23:00:00

0 0

雪糕乐

若是没有n的取值区间超过内存大小这个限制，可以简单的用hash统计次数，排序再还原即可，即使用计数排序。

否则，因为是数字排序，可以使用基数排序，运行时间相对计数排序来说要多一点，但是都是同一级别O(n)。

即计数排序只需扫描一遍原数组，而基数排序需要扫描k遍，k为n个数中最大那个数十进制下包含的位数。显然

在确定的机器下，k是小于某个常数的。

发表于 2019-07-16 16:16:09

1 1

allen :

hash和期数排序有什么关系

发表于 2019-07-16 16:11:19

毛大军

如果是最小的话可以考虑成k个连续的数，然后每次发现一个数值就让数组对应的下标加加

发表于 2018-10-13 11:40:59

0 0

落星辰

桶排序的空间复杂度为O（m+n），m是数组分桶的时间复杂度，n是桶内排序时间复杂度，桶越多，时间复杂度越少。因为n的取值区间长度超过了内存长度，因此此处不能用桶排序

发表于 2018-10-13 11:40:48

0 0

窦先生

类似于计数排序，但是辅助空间（Hash表）的取值可能不是连续的

发表于 2018-10-13 11:40:33

0 0

窦先生

先用哈希函数进行压缩n-k，时间复杂度为O（你），然后进行排序，时间复杂度为O（klogk），数量级为k级别。因此整个排序的时间复杂度为O（n）

发表于 2018-10-13 11:40:14

0 0

小可爱

可以用桶排序，实现复杂度为o（N）

发表于 2018-10-13 11:40:05

0 0

小飞鞋

我的理解是这样的，先是用比较的方式将n个数字，通过hash函数来压缩数据的长度（键值对的形式），花费O（n）；压缩过后，不同的数的个数就是K级别的了，然后进行排序即（O（klogk）或者已经有序O（1）），那么总的复杂度近似为O（n）。

发表于 2018-10-13 11:39:54

0 0

咸鱼王

两两不同的数字的个数为k，因为不知道确定的数字范围，桶排序不适合，又因为 n远远大于k，本题使用hash表来统计，首先获得k个数及其每个数出现的次数，然后对k个数进行排序，排序的复杂度可忽律不计，实际上就是遍历一遍n个数字，所以本位复杂度为O（n）。

发表于 2018-10-13 11:34:31

0 0

问题信息

分类：数据结构 - 时间、空间复杂度

难度:

最新校招难题刷题，快来进刷题群吧