在一个有8个int数据的数组中，找出最大和第二大元素至少需要_创新工场笔试题

推荐

SunburstRun

答案是 B

比如 A B C D E F G H，通过8进4的方式，A与B比较， C与D比较.....然后再4进2，A与C比较（假设A,C比B,D大），E与G比较。再2进1，比如A与E比较（假设A，E比C,G大）选出最大的A，总共7次。

然后次大的数一定是被最大数PK下去的，所以再选B C E三个比较2次得到次大的数

A

A E

A C E G （7次）

A B C D E F G H

再选 BCE中最大的（2次），共9次，不过可以这个方法比较次数是少一点，但是所需要的空间大，要记下与沿途的最大值比较的数。

编辑于 2015-07-23 09:04:53 回复(53)

长期收简历

图片说明

发表于 2017-01-03 10:19:06 回复(28)

Tommyzt

答案是：B

分析：这是一个考最优算法的下界问题。

选择问题的复杂度下界，已经有证明，可参考算法导论或屈婉玲的算法设计与分析技术这本书。

对于选择问题，找最大问题的下界是：n-1

找第二大问题的下界是：n+logn-2

因此，本题，n=8，代入下界公式：8+3-2 = 9，所以选择B.

发表于 2015-09-03 21:57:58 回复(2)

shine_hai

我觉得这题答案有问题，最少可以只要7次，1,2,3,4,5,6,7,8这8个数代表第几个数，首先1,2比较确定较小的数temp，1次，接下来，3和temp相比，假设3比temp，2次，则4再比，以此类推，直到第8个数和temp比，依旧比8小，则1,2就是选出的最小的两个数，而此时只比较了7次，这是最少的次数。

而答案不合理的地方就是，1,2相比，3,4相比，5,6相比，7,8相比，如果其中存在第一和第二相比，则会把真正的第二剔除，例如，7,8是最大和第二大的两个，但是7,8相比，则只剩最大的数，第二大被剔除了，从而接下来得到的最终结果不是正确答案。

发表于 2015-09-02 22:08:12 回复(25)

仲言2015

采用淘汰赛模式，经过三轮4+2+1=7次比较可以确定冠军（最大值）。

再在每轮比赛中曾经和冠军（最大值）比较过的三个数中，通过三次比较可以找出真正的亚军。（次大值）

发表于 2015-04-08 15:35:53 回复(8)

牛客-凌凌漆

类似于比赛一样先是小组赛，然后半决赛，最后决赛；

当然题目是：

A

A E

A C E G

A B C D E F G H

比较次数是 7+ BCE之间的两次比较=9

发表于 2018-10-07 09:53:57 回复(2)

大明白

C

1357 比较三次找到最大的结果1

2468 比较三次找到最大的结果2

结果1与结果2 比则为整个数组最大的

然后剩下的与另外一组没有比过三次第二大的就出来了

发表于 2015-03-12 18:17:31 回复(0)

zt_xcyk

8个数两两比较，比较4次，得到4对数，一大一小。 4个大数比较，比较3次，得到了8个数中最大的。现在第二大数就在其它三个大数里面，（防止最大数和第二大数在一组，直接给刷掉）比较两次，得到第二大数。

编辑于 2020-08-14 11:46:50 回复(4)

卷王张三

选的C 后来看了一下明白了，选第二的时候不需要打擂台这样一个个比较四个，只用比较三个就好了。具体步骤如下：

1. 1-2 ,3-4, 5-6, 7-8, 9-10 一共四次选出最大的四个 A,B,C,D 4次

以下不同的比法，就是产生9次和10次答案的原因了

2. A,B 相比取最大，C,D相比取最大 2次

3. 二中两个最大的相比得到所有数据中最大值 1次

4. 由于最大的值最开始所在组的另一个元素可能是所有元素中第三大的，（比如1是最大，那么最先和1比的2可能是所有数据中第二大的，比之后选出的都要大），所以此时2和B,C,D相比

注意，因为采用的A,B相比，C,D相比的方法，所以可以排除掉最小的一个元素（比如A，胜出的话，C,D相比，输掉的元素肯定没有资格竞争第二大了）所以在这里，其实只有3个元素相比，2，和B,C

自然就是 2次了 所以总的次数是 4+2+1+2 ==9 次

如果 A,B,C,D相比的时候采用打擂台的方式，就是一个个上台挑战A，谁输谁下台，一样是比较3次，但是这样子做，对以后比较第二大的元素有影响，使得多比较了一次是 10 次了

所以只需要取最大的时候，一个个打擂台，后续还需要操作，分批比较

发表于 2016-02-14 16:02:30 回复(1)

linko解万

看了楼下仁兄的见解，毛塞顿开-.-，转回正题。
8个int数组，前四个和后四个分为两组相比，各要相比三次，则已比较了6次，这时两组最大数已出现，再比一次，找出数组中的最大数，此时比较了7次。设前四个数相比的最大数为整个数组的最大数，那么，我们只需要拿后四个数的最大数来和前四个数剩下的三个数相比，就能得出第二个大的数。因为后四个数最大数已经和后4个数都相比较过了，也和前四个数的最大数比较过了，那么前四个数就只剩下3个没和后四个数最大数比较过，可能说得有点不够清楚，不过结果还是毋庸置疑的7+3=10次

发表于 2015-07-17 12:56:20 回复(6)

Ramon_and_I

解析：如图所示：

1. 先一对一对比较，需要 4次，得到2,3,6,7位每组最大值；

2. 再对最大的四个一对一对比较需要 2次，得到3,6位最大值；

3. 再对剩下的两个最大的比较需要 1次，此时最大值已经找到3，显然6就是右边的最大值，所以只需要判断6是不是老二即可；

4. 要判断6是不是老二，只需与左边的老二比较，左边的老二可能是2，也看是4，所以得比较两次。

总共比较次数 = 4+2+1+2 = 9.

发表于 2018-10-23 17:44:14 回复(0)

Wu_Being

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
void getMax1AndMax2(int a[],int& max1,int& max2){
	max2=max1=a[0];
    for(int i=1;i<8;i++){ 
		if(max1<a[i]){
		    max2=max1;
        	max1=a[i];
		}else if(max2<a[i]){
		    max2=a[i];
		}
	}
}

int main(){
	int a[]={2,1,3,8,5,6,4,7};
	int max1,max2;
	getMax1AndMax2(a,max1,max2);
	cout<<max1<<" "<<max2<<endl;
	return 0;
}

编辑于 2016-03-30 15:45:42 回复(0)

Z福♚松子

九次，次大为和最大值比较过的其余三个值中的其中一个

编辑于 2018-04-18 11:33:42 回复(2)

Yeloran

找最大元素需要n-1次比较，找第二大元素需要logn-1次比较

发表于 2022-03-03 15:52:10 回复(0)

听说这样写Java才是老司机

7次选出最大的x，然后去比较跟x比较过的那三个数(三个数比较2次)。故9次

发表于 2021-07-30 12:01:57 回复(0)

牛客167919号

难道不是8次吗？七次就是其他评论里7＋2＋1出来的:比如ABCDEFGH,就近两个比较是4次，两两比较是AC DE ，若A>C D>E ，假如A>D，最后比一次得到最大值A，C和D再比一次就能得到次大值了啊

发表于 2016-05-03 20:24:53 回复(0)

綦晓伟

找出前面部分的最大值 3次

再找出后面部分的最大值，3次

两个最大值相比较只需要3+3+1=7次就可以确定出

发表于 2015-05-05 11:13:20 回复(4)

WherestheLove?

重点是被最大值比下去的所有值都可能是次小值

发表于 2020-06-14 13:48:31 回复(0)

anicy

1. 先将8个数划分为4组，每组两个数（假设最大数在第一组A中），通过两两比较，剩下4个较大的数；比较了4次。

2. 然后将剩下的4个数继续划分为2组，每组两个数（假设最大数现在在B组中）进行比较，剩下2个较大的数；比较了2次。

3. 将剩下的两个数M,N进行一次比较，就得到了最大数M。比较了1次。

4. 将N分别于A组和B组中的数进行比较，就得到了次最大数。比较了2次。

发表于 2015-08-03 22:24:32 回复(0)

铠12138

这题解法可以惨遭锦标赛算法

发表于 2020-07-26 22:51:02 回复(0)

子枫i

第一轮：8个元素分成4份，每份2个元素，两两相比找出每份的最大值，共比较4次，第二轮：然后得出4个元素再分成2份找出每份最大值，共比较2次，第三轮：然后还剩两个元素，比较1次，即可得出最大值，然后再一次进入第二轮，把刚刚找到的最大值去掉，还剩3个元素，比较2次，即可得出次大值，所有总共比较次数为，第一轮的4次+第二轮的2次+第三轮的1次+再一次进入第二轮的2次：4+2+1+2=9次

发表于 2020-06-12 10:31:58 回复(0)

在一个有8个int数据的数组中，找出最大和第二大元素至少需要

问题信息

热门推荐

相关试题