编程之美3：寻找数组中的最大值和最小值以及最大值和次大值

浏览数：13 / 时间：2015年06月08日

很开心，这是今天的第三篇文章啦！下午健身也感觉非常过瘾，托付宿舍妹子从日本代购的护肤品也到了。耳边漂浮着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);
}