前些时候在网上看到小米,百度,微软等公司都有如下的面试题目:
一个数组中有2n+2个整数,其中n个出现了两次,只有2个出现了一次,要写算法(最优)求出这两个独特的数.
解决这个题目我的思考过程如下:
原题中有2个独特的数,如果只有1个独特的数呢?显然,如果只有一个独特的数的话有一种并不通用的解法(全部异或,结果就是那个独特的数).但是,我的想法是利用快速排序的一个partion子过程,每一次partion结束我假设第k个元素是用来进行partion结束之后所在的位子(左边的都比第k个元素小,右边的都不比第k个小),则知道左边有k-1个元素,显然,如果k-1是一个奇数,则我们要找的那个独特的数在左边,否则在右边,这样,每一次parion结束我就能把搜索的空间缩小.
思考:
上面的算法看起来是对的,可是其复杂度呢?(我自己的那种算法,而不是那个一次异或的妙法).如果每一次partion结束之后刚好把搜索的空间去掉了2个元素呢(这是最糟糕的情况,但是,是完全有可能的)?那么我的算法的复杂度就是O(n^2)了,还不如直接一个排序呢,呵呵.
分析:
对于快速排序,我想任何一本书上都会讲到说其复杂度平均情况下是O(NLgN),也就是说,快速排序的平均复杂度是基于比较的排序的极限(不可能再优化了).但是,如果我们的运气非常不好的话,每一次快速排序都使得左边只有一个元素呢,那么复杂度就是O(n^2),只是由于每一次都这样发生的概率实在太低了,所以不管如何,快速排序的平均情况还是比较好的(快速排序的时间复杂度其实就是二叉树的平均高度,而且刚好对应,可以用一棵二叉查找树一一对应一次快速排序).
当然,如果有人故意捣乱呢,如果有人故意安排一个特殊的序列,使得每一次partion刚好分出一个元素,那么我们只能对快速排序说no了.这个问题怎么解决呢?有人就聪明了,在进行快速排序之前对数组进行一次预处理,就是进行一次随机化.(使数组的元素随机排序一次).
问题:
在快速排序之前随机化只能从概率上降低最糟糕的情况,可是,不能从原理上证明不会发生最糟糕的情况---因为随机交换的话有概率(1/n!)使得随机化之后的序列与随机化之前的序列完全一样,这样,故意安排的计划还是可能得逞.
问题的解决方案:
以上的快速排序之所以说可能达到O(n^2),是因为有一种特殊的序列可能导致的,现在的想法是,如果有一种partion,使得划分的结果不可能是c:n-c(即左边只有有限个元素,右边却是几乎所有的元素).刚好我们可以有如下的策略,使得可以在O(n)的复杂度内给出一个最差情况下是0.3:0.7的划分方法,其方法如下(在算法导论P112上有)
把数组分成5个一组(多余出来的不满5个当成一组),然后进行排序,并且找出每一组的中位数,再一步是找出这n/5个中位数中的中位数(一个递归过程),可以知道,其时间方程如下:T(n)=T(n/5)+ O(n),最后由主定理知复杂度是O(n),也就是说,我们能在O(n)的时间内完成以上的过程,设最后找出来的一那个数是x,可知按照x去partion则比例最差是0.3:0.7,也就是说,我们可以得到快速排序的子过程(partion)的一个优化的partion,这个优化的partion会使得在partion之后数组的比例比较协调.
现在按照这个优化之后的partion去解决题目中提出的问题,即找出两个特别的数.
首先,我们要证明的是可以在O(n)复杂度内解决1个特殊的数的问题(那个巧妙的异或算法不允许使用).
我们注意到,对数组的每一次partion(用上面的那个优化的partion)之后,得到两段,如果左边的元素个数是奇数,显然,我们需要在左边找(右边一定全部是出现两次的数),否则,在右边找.则知算法的时间复杂度最差是T(n)=T(0.7n)+O(n),解出来还是O(n),也就是说,解决一个特殊的数的问题需要O(n)即可.
现在解决两个特殊的数的问题.
同样的,对于一次partion,如果左边是奇数个,则知道,左边和右边都刚好有一个特殊的数,此时,显然可以在O(n)内解决,否则,如果左边是偶数个,则把左边的数全部异或,如果结果为0,则右边有两个特殊的数,如果不为0,则两个特殊的数全部在左边,此时方程也是T(n)=T(0.7n)+O(n),解得复杂度是O(n).
以上解决了两个特殊的数的问题,现在把问题扩充如下:
在n个数的序列中(用数组存储,而且不一定是整数),有t(t<k)个数只出现一次,其余m个数都出现k次,要写算法求出这t个特殊的数.(n=t+mk)
算法如下:
仍然用那个优化的partion,一次partion结束后设左边有x个数,如果x被k整除,则要找的t个数全部在右边,此时问题的规模降低为0.7n(至多),否则,这t个数分布在左边和右边,对左边和右边同时进行递归处理.这样,左边和右边都是线性时间(左边O(x),右边O(n-x)),加起来也是线性时间(O(n)).
总结:算法的时间复杂度是O(n),空间是O(lg n)----partion过程的递归空间.
分享到:
相关推荐
了解微软+百度+谷歌+阿里巴巴+腾讯+华为+小米面试题目
整理研究者July博客部分面试笔试题,...微软、谷歌、百度等公司经典面试100题[第101-170题].pdf 微软等数据结构+算法面试100题全部答案集锦.pdf 微软公司等数据结构+算法面试100题(第1-100题)全部出炉.pdf
小米运维面试题目(1)
C++面试题,数据结构,BAT等大公司面试题
里面包含了各大互联网公司的笔试面试题目,有些题目可能比较老,但是知识性的东西永远不会过时,希望对大家参加社招校招有所帮助
BAT京东百度人搜阿里巴巴腾讯华为小米搜狗等各大互联网公司校招面试笔试题面(2015年),240多试面试笔试文档资料:华为校园招聘笔试面试题合集去哪儿网校园招聘笔试面试题合集奇虎360校园招聘笔试面试题合集微软等...
小米嵌入式软件工程师笔试题目解析_嵌入式-常用知识&面试题库_大厂面试真题.pdf
gamesloft C++面试题目.docx Google笔试面试 IQ智力面试题笔试题 JAVA笔试面试资料 NET面试题笔试题 web开发 中兴资料 微软笔试面试 数据库面试题笔试题 百度笔试面试 算法 数据结构 网易搜狐新浪笔试面试 腾讯笔试...
百度阿里腾讯搜狗网易小米等面试题,适合校招的应届生。
小米公司安全工程师岗位面试经历.docx小米公司安全工程师岗位面试经历.docx小米公司安全工程师岗位面试经历.docx小米公司安全工程师岗位面试经历.docx小米公司安全工程师岗位面试经历.docx小米公司安全工程师岗位...
互联网大型公司(阿里腾讯百度等)android面试题目(有答案).pdf 百度校园招聘笔试面试题合集.rar 百度校园招聘笔试题-WEB前端工程师-电子科技大学.pdf Java架构面试专题(含答案)和学习笔记 整套 RAR 超大全压缩包
2020年百度、阿里、腾讯、字节跳动Android高频面试题解析,让你对安卓面试不再茫然。包含Java知识点汇总、Android知识点汇总、Android扩展知识点、Android开源库源码分析、设计模式汇总、Gradle知识点汇总、常见面试...
百度云下载到小米路由器的chrome插件
小米平板和微软surface pro 2哪个好.docx
百度人搜,阿里巴巴,腾讯华为小米搜狗笔试面试八十题.zip
2021年最新(小米)前端面试题真题解析.rar
2017年小米的春招面试面经,很有用,希望对大家有帮助。
百度、京东、搜狗、小米,中兴、迈瑞、绿盟、思特沃克等公司软件测试工程师的面经,包括具体的题目和情景面试题。
百度人搜阿里巴巴腾讯华为小米搜狗笔试面试八十题.zip 百度人搜阿里巴巴腾讯华为小米搜狗笔试面试八十题.zip 百度人搜阿里巴巴腾讯华为小米搜狗笔试面试八十题.zip 百度人搜阿里巴巴腾讯华为小米搜狗笔试面试八十题....
java2018最新华为小米面试题,希望能帮助大家,对java学习的知识能更完善