好贷网好贷款

一道看上去很吓人的算法面试题:如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)

发布时间:2016-12-4 5:58:08 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"一道看上去很吓人的算法面试题:如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)",主要涉及到一道看上去很吓人的算法面试题:如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)方面的内容,对于一道看上去很吓人的算法面试题:如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)感兴趣的同学可以参考一下。

看上去似乎任何已知的算法都无法做到,如果谁做到了,那么所有的排序方法:QuickSort,ShellSort,HeapSort,BubbleSort等等等等,都可以扔掉了,还要这些算法干吗阿,呵呵。不过实际上,在数字范围有限制的情况下,是有一个这样的算法的,只需要用一个数组记录每个数字出现次数就可以了。假定你的数字范围在0到65535范围之内,定义一个数组count[65536](这个空间是常量,和n无关,所以是O(1) ),初值全部为0。那么假设有下面这些数字:10020030011906...那么对于每个这个数字,都做在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)这个算法很简单,相信大家都会,只是这个题太过于变态了,一般会把面试者吓住(我原来面试也出过这个题,只不过题目的表述形式要“友善”的多,呵呵)Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1589603

上一篇:进程编程2 – Unix环境高级编程8章读书笔记
下一篇:相信百度没错!

相关文章

相关评论