我要招人

去企业版

首页 > 试题广场 >

给定一个含N 个不相同数字的数组，在最坏情况下，找出其中最大

[单选题]

给定一个含N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的

数，至少需要 N - 1 次比较操作。则最坏情况下，在该数组中同时找最大与

最小的数至少需要（）次比较操作。（⌈ ⌉表示向上取整，⌊ ⌋表示向下取整）

```
⌈3N / 2⌉ - 2
```
```
⌊3N / 2⌋ - 2
```
```
2N - 2
```
```
2N - 4
```

查看正确选项

鵀橓

同时找最大最小值，有更优化的方法，如果没有学过这个算法，
只能根据题面猜测肯定小于2N-2
结合优化的算法，得到大约是A

发表于 2019-03-15 11:07:54 回复(0)

0x0offer的菜鸡

这个题目是NOIP组的题目，可以分两种情况讨论

（1）n为奇数

算法思路：选定数组第一个元素为最大值max和最小值min，对剩余的n-1个元素按照每两个元素进行分组，首先对每个分组里面的两个元素进行对比，得到当前分组中最大值temp_max和最小值temp_min，然后用最大值max与当前分组中最大值temp_max做对比，用最小值min与当前分组中最小值temp_min做对比，分别更新最大值max和最小值min,按照步长为2，向后推进，直到遍历完数组

比较次数=3*(n-1)/2，解释：每个分组两个元素进行对比，对比次数为n-1/2,得到n-1/2个最大值temp_max和最小值temp_min，再用最小值min与所有的temp_min，最大值max和所有的temp_max做对比得到最后的最大值和最小值，次数都为n-1/2,所以最后总的次数为3*（n-1)/2。

（2）n为偶数

算法思路：对数组按照每两个元素进行分组，取第一个分组中的较大值为最大值max，分组中的较小值作为最小值min，然后用max和剩余n-2/2组产生的temp_max做对比，min和剩余的n-2/2组产生的temp_min做对比，得到最终的最大值和最小值

比较次数：分组中每个组中的两个元素进行对比次数为n/2,用第一组的较大值和剩余n-2/2组的较大值对比，次数为n-2/2,用第一组的较小值和剩余n-2/2组的较小值对比，次数为n-2/2,所以总次数为n/2+(n-2)/2*2=3n/2-2

所以最终答案为A

发表于 2019-11-29 17:15:46 回复(2)

陈皓天

找个数字带进去就行了

发表于 2019-10-18 10:39:01 回复(0)

MC233_

先设N==1然后计算

然后设N==2计算

（然后就知道了

）

发表于 2019-10-16 18:23:48 回复(1)

qicaihuang

A跟B的区别就是一个是向下取整，另一个是向上取整。

发表于 2019-12-27 09:17:03 回复(0)

提交观点

问题信息

OI常识普及排序

上传者：牛客309901号

难度：

5条回答 5收藏 9064浏览

给定一个含N 个不相同数字的数组，在最坏情况下，找出其中最大

问题信息

热门推荐

相关试题