题目：
如何找出一个数组中的最大值和次大值，并且找出它们的位置。
思路：
假设只有四个数字，分成两组，前两个比较一次得出最大和次大，后两个比较一次得出最大和次大，则四个数字的最大值就是两个较大值中的最大值。而次大值就是刚才那两个比较中的较小的和另外一组的次大值比较。举个例子：1 4 3 5 。较大值4 < 较大值5，则5是最大值，然后较大值4 和另一组的次大值3 比较，得出次大值为 4。
对于n个数字的数组来说，可以使用分治递归的方法，得出左右两组中的最大值和次大值，然后利用上面的方法得出最大值和次大值。
代码：
#include<iostream>
#include<vector>
using namespace std;
void maxAndSec(vector<int> &nums , int left , int right , int &Max , int &secMax)
    {
        if(left == right)
        {
            Max = nums[left];            
			secMax = INT_MIN;
            return;
        }
        if(left == right-1)
        {
             secMax = min(nums[right] , nums[left]);
             Max = max(nums[right] , nums[left]);
			 return;
        }
        int mid = (left + right)/2;
        int leftMax = 0 , leftSec = 0 ;
        maxAndSec(nums, left , mid , leftMax , leftSec);
        int rightMax = 0 , rightSec = 0;
        maxAndSec(nums , mid+1 , right , rightMax , rightSec);
        Max = max(leftMax , rightMax);
		if(leftMax < rightMax)
			secMax = max(leftMax , rightSec);
		else
			secMax = max(rightMax , leftSec);
    }

void maxAndSec2(int *nums , int len)
{
	if(len == 0)
		return ;
	int Max = nums[0];
	int secMax = INT_MIN;
	for(int i = 1 ; i < len ; i++)
	{
		if(nums[i] > Max)
		{
			secMax = Max;
			Max = nums[i];
		}
		else
		{
			if(nums[i] > secMax)
			{
				secMax = nums[i];
			}
		}
	}
	cout<<Max<<endl<<secMax<<endl;
}
int main()
{
	int num[7] = {2,4,3,5,6,7,3};
	maxAndSec2(num , 6);
	vector<int> nums(num , num+7);
	int max = 0 , secmax = 0 ;
	maxAndSec(nums,0,6,max,secmax);
	cout<<"最大值是："<<max<<endl<<"次大值是："<<secmax<<endl;
}
	

1. 问题
数组中的最大值和次大值
输入：A[1…n]=<a1, a2, …, an>

输出：max1，max2
【注：max1表示最大值，max2表示次大值】
2. 代码
// max1 和 max2首先均被初始化为int范围内最小值，
// 并且保证数组A[1..n]中的任何一个值比int范围内最小值都大。
for (int i = 1; i <= n; i++) {
	if (A[i] > max1) {
		max2 = max1;
		max1 = A[i];
	} else if (A[i] > max2) {
		max2 = A[i];
	}
}

3. 算法正确性证明
算法证明所用技术：循环不变式
证明要点：

初始化： 首先证明在第3次循环之前，循环不变式成立。即，对于数组中前2 $(3 - 1 = 2)$个数，max1中存储最大值，max2存储次大值。

保持： 证明从第3次循环往后，每次迭代保持循环不变式。即，如果第k次执行之前，循环不变式（对于数组前 $k-1$ 个数，max1中存储最大值，max2存储次大值）成立，第k+1次执行之前，循环不变式（对于数组前 $k+1-1$ 个数，max1中存储最大值，max2存储次大值，）仍然成立。

终止： 最后研究在循环终止时发生了什么。导致循环终止的条件是i <= n。我们有：对于数组中的前n个数，max1存储最大值，max2存储次大值。
我们在这里仅证明保持部分。

第k次执行循环体之前： 对于数组前k-1个数，max1存储最大值，max2存储次大值。

第k次执行循环体： 分支1，若A[k]>max1，则执行max2 = max1; max1 = A[k]。 由于max1存储的是前k-1个数的最大值，因此，前k个数的次大值就是max1，所以将max1的值转存至max2。而将A[k]存入max2，这样，max1存储的就是前k个数的最大值了。分支2，若max1>A[k]>max2，则执行max2 = A[k]。由于max1比A[k]大，所以，前k个数的最大值依然是max1，所以max1的值不变。但A[k]比max2大，并且又因为max2存储的是前k-1个数的次大值，因此比当前max2大的数只有max1和A[k]，又因为max1大于A[k]，所以，A[k]是前k个数的次大值。故需要将A[k]的值转存至max2。

第k+1次执行循环体之前： 对于数组前k个数，max1存储最大值，max2存储次大值。

 

    #include<stdio.h>
    //改数组大小只需要修改 N后面的数字
    #define N 5


	int main(void)
    {

	int arr[N]={5,6,8,3,9};
		
	int max= 0;  //定义最大值并赋值
	int mid= 0;  //定义次大值并赋值
	for(int i = 0;i<N;i++){
	    /*因为arr[i]是固定的 ，所以可以用arr[i]先和max比较，如果大于max 则
		把max的值赋给mid的值，然后把arr[i]赋给max  这样max肯定比mid大*/	
	    if(arr[i]>max)
        {
	        mid = max;
	        max =arr[i];
	    }else if(arr[i]>mid)
        {
            /*  另一种情况 arr[i]处于两者之间*/
	    	mid = arr[i];//  则吧arr[i]赋给mid
	    }
	}
	printf("max=%d,mid=%d\n",max,mid);
	return 0;
	}


 

 

 

很开心，这是今天的第三篇文章啦！下午健身也感觉非常过瘾，托付宿舍妹子从日本代购的护肤品也到了。耳边漂浮着Hebe田馥甄的《魔鬼中的天使》文艺的声线，一切都好棒，O(∩_∩)O哈哈~。爱生活，爱音乐，爱运动，额，当然还有要爱学习啦！加油↖(^ω^)↗

额，扯远了。第三篇是关于寻找数组中的最大值和最小值。第一次看到这个题目的时候，楼主稍微鄙视了一下，因为觉得这个题目有什么好做的。但是楼主还是看了看《编程之美》上的写的，发现还是有必要记录一下，不一样的思考方式。很赞！大家和楼主一起哦，Are you ready?呼呼(～ o ～)~zZ



题目一：寻找数组中的最大值和最小值

解法一

把寻找数组中的最大值和最小值看成是两个独立的问题，对于每个独立的问题的话，我们可以采用一次循环遍历的方法得到。假设数组的长度为N，那么总共需要比较的次数为2N。解法过于简单，代码略过啦。

解法二

假设数组为[5, 6, 8, 3, 7, 9]，

每相邻的两个元素比较，较大者放在偶数位，较小者放在奇数位。完成这一步骤后，偶数位为6， 8， 9。奇数位为5， 3， 7。
然后遍历偶数位可以获得数组的最大值，遍历奇数位可以获得数组的最小值。
比较次数：0.5N+0.5N+0.5N=1.5N看代码：
#include <iostream>  
#include<limits>

using namespace std;  

void partion(int *pArray, int len);

int main()  
{  
    int a[] = {1, 2, 3, 4, 5, 6, 0, 7};
    int len = sizeof(a) / sizeof(int);
    partion(a, len);
    int MAX = a[0];
    int MIN = a[1];

    int i = 0;
    int j = 1;

    for (; i < len - 1, j < len; i = i + 2, j = j + 2)
    {
        if (a[i] > MAX)
        {
            MAX = a[i];
        }
        if (a[j] < MIN)
        {
            MIN = a[j];
        }
    }

    //说明有一个数单出来
    if (i == len - 1)
    {
        if (a[i] > MAX)
        {
            MAX = a[i];
        }
        if (a[i] < MIN)
        {
            MIN = a[i];
        }
    }

    cout << "最小值为" << MIN << " 最大值为" << MAX << endl;
    system("pause");
}  

//将数组分成两个子数组，较大值放在偶数位，较小值放在奇数位
void partion(int *pArray, int len)
{
    int i = 0;
    while (i < len - 1)
    {
        //如果奇数位的比偶数位的大，则交换位置
        if ((pArray[i + 1] > pArray[i]))
        {
            swap(pArray[i + 1], pArray[i]);
        }
        i += 2;
    }
}

解法三

解法二虽然降低了比较的次数，可是却破坏了数组的顺序。绝大多数时候，我们只是想获取数组中的最大值和最小值，并没有想要改变数组的顺序，所以解法二，会有问题。那这就是解法三改进的点了，同样和解法二一样，每相邻的两个元素进行比较，但是不改变数组的顺序。而是选择用两个变量，如MAX和MIN来记录最大值和最小值并看情况更新。看下图所示 


看代码：

#include <iostream>  
#include<limits>

using namespace std;  

void searchMinAndMax(int *pArray, int low, int high, int *MIN, int *MAX);

int main()  
{  
    int a[] = {9, 8, 7, 6, 5, 4, 3, 11, 12, 13, 1, 1, 13, 67, 89, 0,100, -1};
    int len = sizeof(a) / sizeof(int);
    int MIN = numeric_limits<int>::max();;
    int MAX = 0;
    int tempMin = 0;
    int tempMax = 0;
    int i = 0;
    while (i < len - 1)
    {
        if ((a[i] >= a[i + 1]))
        {
            tempMax = a[i];
            tempMin = a[i + 1];
        }
        else
        {
            tempMax = a[i + 1];
            tempMin = a[i];
        }
        if (tempMax > MAX)
        {
            MAX = tempMax;
        }
        if (tempMin < MIN)
        {
            MIN = tempMin;
        }
        i += 2;
    }
    if (i == len - 1)
    {
        if (a[i] < MIN)
        {
            MIN = a[i];
        }
        if (a[i] > MAX)
        {
            MAX = a[i];
        }
    }

    cout << "最小值为" << MIN << " 最大值为" << MAX << endl;
    system("pause");
}  

解法四

分治法，把N个元素的最大值和最小值问题，分别求出N/2维左半部分和右半部分的最大值和最小值。左半部分最大值和右半部分最大值比较，较大值为最后的最大值；同样，左半部分的最小值和右半部分的最小值比较，较小者为最后的最小值。看代码：



#include <iostream>  

using namespace std;  

void searchMinAndMax(int *pArray, int low, int high, int *MIN, int *MAX);

int main()  
{  
    int a[] = {9, 8, 7, 6, 5, 4, 3, 11, 12, 13, 1, 1, 13, 67};
    int len = sizeof(a) / sizeof(int);
    int MIN = 0;
    int MAX = 0;
    searchMinAndMax(a, 0, len-1, &MIN, &MAX);
    cout << "最小值为" << MIN << " 最大值为" << MAX << endl;
    system("pause");
}  

void searchMinAndMax(int *pArray, int low, int high, int *MIN, int *MAX)
{
    int middle = (low + high) / 2;

    //如果分组只剩下两个数字或者一个数字，则直接比较
    if (high - low <= 1)
    {
        if (pArray[low] > pArray[high])
        {
            *MIN = pArray[high];
            *MAX = pArray[low];
            return;
        }
        else
        {
            *MIN = pArray[low];
            *MAX = pArray[high];
            return;
        }
    }

    int lMin = 0;
    int lMax = 0;
    int rMin = 0;
    int rMax = 0;

    searchMinAndMax(pArray, low, middle, &lMin, &lMax);
    searchMinAndMax(pArray, middle + 1, high, &rMin, &rMax);

    *MIN = min(lMin, rMin);
    *MAX = max(lMax, rMax);
}

需要比较的次数为1.5N−2。

题目二：寻找数组中的最大值和次大值

这道题是《编程之美》上题目一的扩展问题，为了巩固前面的知识，楼主决定把这道题也给做了，运用分治思想。主要思想和题目一类似。直接看代码：



#include <iostream>  

using namespace std;  

void searchMinAndMax(int *pArray, int low, int high, int *MIN, int *MAX);

int main()  
{  
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 67};
    int len = sizeof(a) / sizeof(int);
    int MAX = 0;
    int SECONDE_MAX = 0;
    searchMinAndMax(a, 0, len-1, &SECONDE_MAX, &MAX);
    cout << "最大值为" << MAX << " 次大值为" << SECONDE_MAX << endl;
    system("pause");
}  

void searchMinAndMax(int *pArray, int low, int high, int *SECONDE_MAX, int *MAX)
{
    int middle = (low + high) / 2;

    //如果分组只剩下两个数字或者一个数字，则直接比较
    if (high - low <= 1)
    {
        if (pArray[low] > pArray[high])
        {
            *SECONDE_MAX = pArray[high];
            *MAX = pArray[low];
            return;
        }
        else
        {
            *SECONDE_MAX = pArray[low];
            *MAX = pArray[high];
            return;
        }
    }

    int lSeMax = 0;
    int lMax = 0;
    int rSeMax = 0;
    int rMax = 0;

    searchMinAndMax(pArray, low, middle, &lSeMax, &lMax);
    searchMinAndMax(pArray, middle + 1, high, &rSeMax, &rMax);

    *SECONDE_MAX = max(lSeMax, rSeMax);
    *MAX = max(lMax, rMax);
}

比较次数也是1.5N−2

楼楼这篇文章就到此为止啦，还剩下三篇就可以开专栏了哦。加油加油！！！希望大家一天都充满活力，O(∩_∩)O哈哈~