1669人阅读
基础算法（160）
编程之美——寻找数组中的最大值和最小值
问题描述：给出一个数组，包含N个整数，那么需要比较多少次找到最大值和最小值
注意：要想得到最大值和最小值，遍历一遍数组是不可避免的。我们能减少的就是减少比较次数来提高效率
方法一、遍历一遍数组，同时得到最大值和最小值
具体是，定义一个max 和 min，每遍历一个数，就分别和max 和 min比较一次，直到处理完所有的数据
比较次数：&N+N = 2N
我们可以把数组中的数据两两分组，分组内找出最大值 和 最小值，之后在最大值的那部分找出最大值，在最小值那部分找出最小值
比较次数：
两两比较，较小值放到左边，较大放右边，这时比较N/2次
之后，得到的最大值部分是 N/2个数，最小值部分是N/2个数
之后在 最大值部分 取出最大值。比较次数N/2
& &在 最小值部分 取出最小值。比较次数N/2
比较次数：&1.5N
评价：虽然比较次数下降了，但是破坏了原数组，而且由于在比较过程中有数据的交换，效率还是会拖累的。（这个方法代码没写了）
方法三、引入俩变量min 和 max，每次也是处理两个数据，直到所有的数据全部都处理完
具体思路：
引入两个变量Min 和 Max
取出两个数，比较一次，得出最大值和最小值
最大值和Max比较，最小值和Min比较，如果比最值还要大或小，则进行更新
比较次数：每处理两个数，比较3次，则N/2 *3 = 1.5N次
优点，不会破坏原数组，较好
方法四、使用分治算法，其实和方法三是一样的，分治是一直到两个数的时候才做，且做完了 把结果合并下就好
思路：在N个数中求最大值和最小值，我们只需求出前后N/2个数的Min和Max，然后取较小的Min，较大的Max即可
比较次数：和方法三一样，比较次数没有变化
f(2) = 1;&
f(n) = 2*f(n/2) + 2;&
&第2个2的意思是：递归分成的两部分求出最值后，还有结合下求出一个整体的最值，这时要有两次比较&
可以推出f(n) = 1.5*n -2; &可见总的比较次数仍然没有减少。
上面所有方法的测试代码如下：
#include&iostream&
#include&vector&
template&typename T&
//方法一的代码
bool MaxMin(std::vector&T& array,T* max,T* min)
& if(array.size()&1)
& *max=array[0];
& *min=array[0];
& size_t array_size=array.size();
& for(int i=1;i&array_i++){
&if(array[i]&*max){
&*max=array[i];
&else if(array[i]&*min){
&*min=array[i];
//方法二的代码
template&typename T&
bool MaxMin_1(std::vector&T& array,T* max,T* min)
& if(array.size()&1)
& &*max=array[0];
& &*min=array[0];
& &int index=1;
& &int array_size=array.size();
& &while(index&array_size&&index+1&array_size)
& if(array[index]&array[index+1]){
& if(array[index]&*max){
& *max=array[index];
& if(array[index+1]&*min){
& *min=array[index+1];
& if(array[index+1]&*max){
& *max=array[index+1];
& if(array[index]&*min){
& *min=array[index];
& index+=2;
& &//如果数组时奇数个的时候，需要将前面的max和min与最后一个数进行比较
& &if(index&array.size()){
& if(array[index]&*max){
& *max=array[index];
& if(array[index]&*min){
& *min=array[index];
//方法四的代码
template&typename T&
bool MaxMin_2(std::vector&T& array,int start,int end,T* max,T* min)
& if(end-start&1)
& & MaxMin_2(array,start,(start+end)/2,max,min);
& & MaxMin_2(array,(start+end)/2+1,end,max,min);
&if(array[end]&array[start]){
&if(array[end]&*max){
&*max=array[end];
&if(array[start]&*min){
&*min=array[start];
&if(array[start]&*max){
&*max=array[start];
&if(array[end]&*min){
&*min=array[end];
//如果是数组是奇数个，采取下面的MaxMin_3，其实上面的MaxMin_2也可以判断。
template&typename T&
bool MaxMin_3(std::vector&T& array,int start,int end,T* max,T* min)
& if(end&start)
& & MaxMin_2(array,start,(start+end)/2,max,min);
& & MaxMin_2(array,(start+end)/2+1,end,max,min);
&if(array[start]&*max){
&*max=array[start];
&if(array[start]&*min){
&*min=array[start];
int main(int argc,char **argv)
& const int ArraySize=5;
& std::vector&int&
& array.push_back(2);
& array.push_back(4);
& array.push_back(3);
& array.push_back(6);&
& array.push_back(1);
& int max,
& MaxMin(array,&max,&min);
& cout&&max&&& &&&min&&endl；
& MaxMin_1(array,&max,&min);
& cout&&max&&& &&&min&&
& MaxMin_2(array,0,4,&max,&min);
& cout&&max&&& &&&min&&
& MaxMin_3(array,0,4,&max,&min);
& cout&&max&&& &&&min&&
& return 0;
找出N个数组中第二大的数，需要比较多少次呢？
是否可以通过类似的分治思想来降低比较次数呢？
方法一、比较笨的方法
先找到本数组中的最大数X，需要n-1次比较，再在剩下的数组中去找最大数X’,需要n-2次比较
则X’就是第二大的数，这需要(n-1) + (n-2)次比较
方法二、我们也可以在数组中，两数结合，分别求出最大值 和 次大值，之后每两个数结合求出的最值 在相互比较，得到最值得最大值 和 次大值
具体思路：
把数组中的每两个元素分为一组，每组中的最大数为F，第二大数为S。
假设相邻两组的最大数和第二大数分别是:Fleft,Si 和&Fright,Sj,。
则这两组合并为一组后，其中最大数和第二大数可能是：
1、若Fi&& Fj，则最大数是Fi；
& & &&若Si &Fj，则第二大数是Si；否则，第二大数是Fj
2、若Fi& Fj，则最大数是Fj
& & &&若Fi&Sj，则第二大数是Fi；否则，第二大数是Sj
比较次数：共有N/2组，每组需要比较倆次得出本组的最大数和第二大数；共需比较N/2 * 2次。
方法三、分治法
思路：和上面的思路是一样的
把数组分成两部分，其最大数和第二大数分别是:Fleft，Sleft，Fright，Sright。合并时的情况可能为：
1、Fleft & Fright，最大数是Fleft；若Sleft&Fright，则第二大数是Sleft，否则第二大数是Fright；
2、Fleft & Fright，最大数是Fright；若Fleft&Sright，则第二大数Fleft，否则第二大数是Sright。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：849255次
积分：16707
积分：16707
排名：第433名
原创：812篇
转载：210篇
评论：136条
1.7 本科 计算机科学与技术 4.3 硕士 计算机系统结构。目前已签约国内某大型互联网公司。联系QQ：
(12)(2)(12)(12)(14)(21)(4)(7)(6)(3)(20)(18)(14)(17)(15)(6)(17)(2)(10)(11)(14)(4)(11)(5)(7)(4)(8)(14)(8)(12)(5)(9)(3)(1)(3)(1)(19)(62)(45)(45)(31)(31)(57)(46)(22)(55)(81)(65)(19)(28)(16)(4)(23)(14)(8)(9)(8)2211人阅读
这个也算是比较好用的一个模版函数吧...
#include &stdio.h&
#include &string.h&
#include &stdlib.h&
#include &iostream&
#include &algorithm&
#include &time.h&
int main()
int a[100];
for(int i=1;i&=10;i++)
int *p=max_element(a+1,a+10+1);
int *q=min_element(a+1,a+10+1);
printf(&%d %d \n&,*p,*q);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：243573次
积分：6046
积分：6046
排名：第3136名
原创：369篇
转载：10篇
评论：35条
(1)(2)(27)(1)(1)(9)(10)(15)(20)(34)(33)(4)(22)(25)(33)(14)(13)(1)(21)(17)(1)(42)(34)c++去掉最大值和最小值求平均数定义一个含 20 个元素的一维整型数组,从键盘上输入 20 个元素,求去掉最大值和最小值以后那些元素的平均值.注:最大、最小元素值可能不止一个,都应该去掉.
#includeint main(){\x09int a[20];\x09int sum=0;//20个数的和\x09int num=20;//数字总个数\x09for(int i=0;i>\x09\x09a[i]=\x09\x09sum+=\x09}\x09int max=a[0];\x09int min=a[0];\x09for(int i=0;imax)\x09\x09\x09max=a[i];\x09\x09if(a[i]
为您推荐：
其他类似问题
扫描下载二维码C++数组求最大值及最小值最快方法（3[n/2]的时间效率）
//最小值和最大值的求解，时间复杂度最多是3[n/2],依据算法导论第九章.
void swap(int &a,int &b)
int temp =
void Grial(int a[],int n)
int i = 0;
if(a[i]&a[i+1])
swap(a[i],a[i+1]);
for(int j = i+2;ja[j+1])
if(a[j]&a[1])
swap(a[j],a[1]);
if(a[j+1]a[1])
swap(a[j+1],a[1]);
if(n%2!=0 && j==n-3)
if(a[n-1]a[1])
swap(a[n-1],a[1]);
cout&<a[0]<
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467142',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'}