【编程题目】如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)
2024-10-18 18:24:40
转自:http://blog.csdn.net/vast_sea/article/details/8167968
看上去似乎任何已知的算法都无法做到,如果谁做到了,那么所有的排序方法:QuickSort,ShellSort,HeapSort,BubbleSort等等等等,都可以扔掉了,还要这些算法干吗阿,呵呵。不过实际上,在数字范围有限制的情况下,是有一个这样的算法的,只需要用一个数组记录每个数字出现次数就可以了。
假定你的数字范围在0到65535范围之内,定义一个数组count[65536](这个空间是常量,和n无关,所以是O(1) ),初值全部为0。
那么假设有下面这些数字:
100
200
300
119
0
6
...
那么对于每个这个数字,都做在count中记录一下:
100
=> count[100]++
200 => count[200]++
300 => count[300]++
119
=> count[119]++
0 => count[0]++
6 =>
count[6]++
...
最后,遍历一边所有这些数字就可得到0~65535每个数字的个数(在count数组中),然后再顺序遍历count数组,count[n]
= m,则输出m个n,(比如说有count[3] = 2,
那么说明有2个数字3),依次输出,最后可得结果。第一次遍历是O(n),第二次遍历是O(1),为常量,所以最后的时间复杂度为O(n),而空间复杂度为O(1)
这个算法很简单,相信大家都会,只是这个题太过于变态了,一般会把面试者吓住
最新文章
- 利用rebase来压缩多次提交
- Centos下安装和配置SVN
- nginx的优化
- ASP.NET MVC使用Bootstrap系统(2)——使用Bootstrap CSS和HTML元素
- 利用StringList对象来管理这些动态生成的对象
- 河南省第八届ACM程序设计大赛
- Markdown 五分钟速成
- 在PLSQL中不能使用中文作为查询条件查询数据
- 关于伪类元素:before和:after
- 手机端 zepto tap事件穿透
- VS2010 断点无效肿么办?
- webpack es6支持配置
- ASP.NET中读取excel内容并显示
- android学习日记26--AIDL之进程间的通信
- 扩展Session机制
- 解决后端动态生成css时无法调用
- 设计模式 单例模式(Singleton) [ 转载2 ]
- RocketMQ初步应用架构理论
- 使用asp.net mvc引擎开发插件系统
- python爬虫-上期所持仓排名数据爬取