首页 > 试题广场 > 给定一个含N 个不相同数字的数组,在最坏情况下,找
[单选题]
给定一个含N 个不相同数字的数组,在最坏情况下,找出其中最大或最小的
数,至少需要 N - 1 次比较操作。则最坏情况下,在该数组中同时找最大与
最小的数至少需要( )次比较操作。(⌈ ⌉表示向上取整,⌊ ⌋表示向下取整)
  • ⌈3N / 2⌉ - 2
  • ⌊3N / 2⌋ - 2
  • 2N - 2
  • 2N - 4
找个数字带进去就行了
发表于 2019-10-18 10:39:01 回复(0)
先设N==1然后计算
然后设N==2计算
(然后就知道了
发表于 2019-10-16 18:23:48 回复(0)
  • 同时找最大最小值,有更优化的方法,如果没有学过这个算法,
  • 只能根据题面猜测肯定小于2N-2
  • 结合优化的算法,得到大约是A
发表于 2019-03-15 11:07:54 回复(0)
A跟B的区别就是一个是向下取整,另一个是向上取整。
发表于 2019-12-27 09:17:03 回复(0)
这个题目是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 回复(0)