旅途

如果想飞得高,就该把地平线忘掉

在一个随机数组中同时求出最大值与最小值

在一个随机数组中同时求出最大值与最小值,要求 辅助空间 O(1)【线性复杂度】,最坏情况下比较次数 3n/2, n为数组元素数


提供一个方法:

假设待处理的数组为A[1...N],该算法分为两步
1. 对A中的元素做如下的比较,A[1]与A[N],A[2]与A[N-1],..., A[N/2]与A[N-N/2+1](如果N为奇数,则A[N/2+1]没有参与比较),对于每一个A[i]与A[N-i+1],如果A[i]>A [N-i+1],则交换他们的值,否则,保持他们的值不变。
2. 第一步的结果是将数组A分成两半,可以证明,最小值一定在前一半中,而最大值一定在后一半中。分别对前一半求最小值,对后一半求最大值,即得到整个数组的最大值和最小值。

对于第一步,比较次数为n/2,第二步的比较次数为n,因此整个算法的比较次数为3n/2(该算法需要严格的3n/2次比较,可能还存在更优的算法,不过暂时没想到)


posted on 2007-09-06 01:55 旅途 阅读(2819) 评论(0)  编辑 收藏 引用 所属分类: C/C++


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理