从1亿个整数中找出最大的1万个

这是比较常见的一个面试题了.

 

看到一篇比较好的文章,留下网址和阅读笔记.

地址:http://blog.csdn.net/shadowkiss/archive/2008/12/19/3557873.aspx

 

其中针对问题,算法上进行不断地优化,是一大亮点,其优化过程包括:

 

不假思索
        stupid,[选择排序]每次找出余下数组中最大的,重复1万次. 

 

稍作思考
        快排后,提取前一万个.
 
深入思考
        最先抽取头部1万个整数作为resultArr(排序后,找出其中最小数),之后遍历余下数据BigArray,发现有比最小数据大的,覆盖之,并重新找出最小元素,如此反复,直至bigArray遍历完全.
        ps.最小元素的查找是优化重点,注意缩减查找范围.下面的优化都集中在这里.

 

深思熟虑
        最小元素的查找在一定范围内进行,先按左大右下排列初选出的ResultArr数组,第一次最小元素指向ResultArr的尾端,每替换一次,后移一位,查找范围加一.

 

苦思冥想
        每次的替换操作会导致resultArr无序,在替换一定次数后,重新整理resultArr,用归并使之有序.

 

殚思极虑
        替换操作 只会导致尾部局部数据无序,只需先排序该部分数据,之后进行有序数据的合并.

 

ps.以上都是我自己阅读后的缩写,留待日后复习之用,很难想象不认真阅读原文能看出任何体会.

 

ps2.当然了,我自己也有一个思路完全不同的解法,主要思想是以快排为原型,但稍作修改.

       每次按快排寻找到支点后(按从小到大),对支点左右的element个数进行判断,如若右边个数小于需要找出的元素个数,则只对支点左边的数组递归调用快排.如此反复,直至右边元素达到指定个数.至于实际的代码实现,待完成

 

 

 

评论

1 楼 beefcow 2015-12-26  

翻到了自己来感慨下，当时写这篇文章的时候只是零敲碎打的看了下面试相关的算法数据结构，今天回来看看，很有之间树叶不见森林的感慨。也算是见证了自己的变化吧。

提到的那篇帖子最后的终极解法是这样的：

先拿出一万个数，排序，之后遍历剩下的元素，每当遇见比这一万个数里最小的数大时，swap，当然这样不断 swap，一万个数里只能左半边还是有序的，右半边会乱序，所以每次要找出这样一万个数里最小的数，得遍历无序的右边。

所以其实最坏情况下,当最初选出的一万个数刚好就是最小的一万个数时，很快，这个一万的数组会被 swap 成完全无序的状态，这时候，每次都得遍历一遍才能找出数组里最小的值，所以复杂度是 N* K

而当年我ps出的解法才是更优解，其实就是 quick sort 的变种（当年姿势虽然匮乏，头脑还是挺灵活的），这样平均复杂度是 N*lg (N/K)  (存疑)

或者直接用 heap，复杂度是 N * lg(K)