首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
给定一个含N 个不相同数字的数组,在最坏情况下,找出其中最大
[单选题]
给定一个含N 个不相同数字的数组,在最坏情况下,找出其中最大或最小的
数,至少需要 N - 1 次比较操作。则最坏情况下,在该数组中同时找最大与
最小的数至少需要( )次比较操作。(⌈ ⌉表示向上取整,⌊ ⌋表示向下取整)
⌈3N / 2⌉ - 2
⌊3N / 2⌋ - 2
2N - 2
2N - 4
查看正确选项
添加笔记
求解答(19)
邀请回答
收藏(5)
分享
纠错
5个回答
添加回答
1
鵀橓
同时找最大最小值,有更优化的方法,如果没有学过这个算法,
只能根据题面猜测肯定小于2N-2
结合优化的算法,得到大约是A
发表于 2019-03-15 11:07:54
回复(0)
7
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)
2
陈皓天
找个数字带进去就行了
发表于 2019-10-18 10:39:01
回复(0)
1
MC233_
先设N==1然后计算
然后设N==2计算
(然后就知道了
)
发表于 2019-10-16 18:23:48
回复(1)
0
上岸即改名
A跟B的区别就是一个是向下取整,另一个是向上取整。
发表于 2019-12-27 09:17:03
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
OI常识
普及
排序
上传者:
牛客309901号
难度:
5条回答
5收藏
9120浏览
热门推荐
相关试题
下列说法中正确的是() 。
硬件
普及
C++
Pascal
选择题
评论
(0)
在所有排序方法中,关键字比较的次数...
计算机常识
排序
普及
C++
Pascal
选择题
评论
(0)
Windows98中,通过查找命令...
计算机常识
普及
C++
Pascal
选择题
评论
(0)
属于组合逻辑电路是()。
数字电路
评论
(1)
如果通过这次面试我们单位录用了你,...
岗位认知
自我认知
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题