面试算法题:16个数,最多用20次比较,找出第二大的数?

这道题最笨的方法就是先从16个数中选出最大的数,然后再从剩下的15个数中选出最大数就可得到答案,因此,需要15+14=29次比较。

既然这道题要求在20次比较之内就能找出第二大的数,那我们就想能简单的方法。

假设16个数中最大的是A,第二大的是B。

首先将16个数两两进行比较,较大者胜出,然后再在胜出者中进行两两比较,按此方法,最后选出最大数A,如下所示

红色路线是最大数经过的路径。

接下来分析B可能存在的位置。

将16个数分为左部分和右部分各8位:

1、如果A和B在两个不同的部分(A在左部分,B在右部分,则B是右部分的最大者),因此按照上面的比较方法,B将在根节点的右子节点,即图中红色1节点;

2、如果A,B处于同一个部分(假设都在左部分,如果同在右部分,分析方法一样),则在左部分的8个节点中,按照方法1继续划分查找;

通过这种方式分析可以知道,A和B一定会做一次比较(想想为什么)。在图中,如果A按照红色路线上升,则B可能出现的位置就是红色节点1,2,3,4。

四个红色位置比较要3次。

因此最终需要:

8+4+2+1+3=18

时间: 03-20

面试算法题:16个数,最多用20次比较,找出第二大的数?的相关文章

C++经典面试算法题

转自:http://blog.csdn.net/f_r_e_e_x/article/details/50770907 1 //1.实现strcpy. 2 char* MyStrCpy( char *pDest, const char *pSrc ) 3 { 4 if( nullptr == pDest || nullptr == pSrc ) 5 { 6 return nullptr; 7 } 8 if( pDest == pSrc ) 9 { 10 return pDest; 11 } 12

给出一个长度为n的数列,请对于每一个数,输出他右边第一个比他大的数。n<=100000.

RT,一个ppt里看到的题,不过没讲做法.百度上基本搜不到.自己想了个做法,理论上可行,复杂度也是O(nlogn). 首先,做一次RMQ,求区间最大值. 对于任意一个数s[i],可以用logn的时间求出他右边第一个比他大的数: RMQ[i][j] 表示从s[i]开始的2^j个数中的最大值.对于确定的i,RMQ[i][j]随着j的增大肯定是非降的. 先判断无解的情况,只要看max(RMQ[i][j],RMQ[n-2^j+1][j]) ,也就是区间[i,n]的最大值是否比s[i]大即可(下面求区间最

一道看似非常难的面试算法题

这是昨天面试百度时碰到的一道算法题:任意数分三组,使得每组的和尽量相等.由于时间仓促,加之面试时头昏脑涨,这道题没做出来甚至没有给出思路,这让我多少有些遗憾和不甘.因为最近接触算法的东西较多而且本身对算法感兴趣,所以回家之后绞尽脑汁想把这题做出来.其实刚看到这题时感觉不难,但是因为数字个数及数值的不确定,我感觉这题越想越难.昨天一晚上没有睡好,甚至做梦都在想这题! 今天上午在多个群里问了这题,都没有给出思路,真是绝望至极.很多人都说 n/3 的思路,其实这种思路一开始就是死胡同.本人属于那种不会

百度面试算法题

1.代码编译过程 在cpp文件中展开include文件. 将每个cpp文件编译为一个对应的obj文件. 连接obj文件成为一个exe文件(或者其它的库文件) 2.100W个整数中求最小的k个数,有哪些方法,优缺点 快速排序: 分区时,根据数P将数组分为两部分,设大于P的数个数为a,小于P的数的个数为b.如果,a>=k,则从这a个数取最大的k个数,若a<k,则从b个数取最大的k-a-1个. 3.两个10G的文件中,求含有相同整数,有哪些方法,优缺点 (1)快排+二分查找 (2)位图法 位图法的应

[面试算法题重做]翻转句子中单词的顺序

话说工作中算法用的真的多么?????? 虽然工作中用不到,但是你总得换工作吧,防不住笔试面试中问你些这么个玩意. 而且,多思考,有助于活跃头脑了.深深扎入项目中童鞋们还可以活跃活跃,防止生锈. 话不多说,题目如下: 题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变.句子中单词以空格符隔开.为简单起见,标点符号和普通字母一样处理. 例如输入“I am a student.”,则输出“student. a am I”. 在何海涛的日记中,分析方法是 先颠倒句子中的所有字符.这时,

面试算法题:爬楼梯,N级楼梯有多少种走法?

By Long Luo 个人博客链接 最近去面试时,在一家小公司面试时,公司小BOSS给我出了一道算法题: 一个人爬楼梯,一步可以迈一级,二级,三级台阶,如果楼梯有N级,要求编写程序,求总共有多少种走法. 这个问题应该是一个很老的题目了,用中学数学来说,就是一个排列组合问题.当时拿到这个题目之后,首先想到使用递归的思想去解决这个问题: N级楼梯问题可以划分为:N-1级楼梯,N-2级楼梯,N-3级楼梯的走法之和. 先计算下0,1,2,3及楼梯有多少种走法: 1 --> 1 2 --> 11 2

常考面试算法题之暴力枚举

结合2017春招和秋招真题,以下几类算法题最常考,汇总了一下: 好多鱼! 牛牛有一个鱼缸.鱼缸里面已经有n条鱼,每条鱼的大小为fishSize[i] (1 ≤ i ≤ n,均为正整数),牛牛现在想把新捕捉的鱼放入鱼缸.鱼缸内存在着大鱼吃小鱼的定律.经过观察,牛牛发现一条鱼A的大小为另外一条鱼B大小的2倍到10倍(包括2倍大小和10倍大小),鱼A会吃掉鱼B.考虑到这个,牛牛要放入的鱼就需要保证: 1.放进去的鱼是安全的,不会被其他鱼吃掉 2.这条鱼放进去也不能吃掉其他鱼 鱼缸里面已经存在的鱼已经相

偶然看到的面试算法题_最短时间找出十包粉末中的两蓝粉末。

题目:有4个杯子,10包粉末,其中有2包溶于水变蓝,其余无色,粉末溶于水2min才能显现颜色.求找出两包蓝色粉末的最短时间.假设水和粉末用不完. 解:以下给出四种解法,标记10包粉末为(1,2 ... ) 杯子为[1,2,3,4]首先我想会不会是有某种算法,dp 二分..@[email protected]..没有,懵懵的. 法一:这是我最初想到的比较傻的方法 第一趟:[12,34,56,78] 每个杯子分别放两包加水融化,剩下两包不管.可能的情况: (1)0个杯子变色,说明剩下两包就是蓝粉末

今天看到别人的面试算法题,求找出十包粉末中两包蓝色粉末的最短时间

题目:有4个杯子,10包粉末,其中有2包溶于水变蓝,其余无色,粉末溶于水2min才能显现颜色.求找出两包蓝色粉末的最短时间.假设水和粉末用不完. 方法一: 第一趟:[12,34,56,78] 每个杯子分别放两包加水融化,剩下两包不管.可能的情况: (1)0个杯子变色,说明剩下两包就是蓝粉末 (2)1个杯子变色,则蓝粉末在这个杯子两包和未融化的两包其中两包,第二趟四包融化一定可以找到 (3)2个杯子变色,则在这两个杯子的四包粉末中,第二趟可找到. 时间均值:E = 2*1/45 + 4*44/45