python/C++课程/第十课逻辑表达式和条件表达式/max_min.cpp

#include <iostream>
#include "limits.h"
using namespace std;

int main() {
    int d[] = {9, 6, 7, 5, 13, 6, 2};
    int n = 8;
    int max = INT_MIN;
    int min = INT_MAX;
    bool flag = false;
    if(n % 2) {
        n--;
        flag = true;        
    }   
    for(int i = 0; i < n-1; i+=2) {
        if(d[i] <= d[i+1]) {
            if(d[i] < min)
                min = d[i];
            if(d[i+1] > max)
                max = d[i+1];
        }
        else {
            if(d[i] > max)
                max = d[i];
            if(d[i+1] < min)
                min = d[i+1];
        }   
    }
    //若数组长度为奇数，还需要和最后一个数作比较 
    if(flag) {
        if(d[n] < min)
            min = d[n];
        if(d[n] > max)
            max = d[n]; 
    }
    cout << "The max value of the array is: " << max << endl;
    cout << "The min value of the array is: " << min << endl;   
} 

/*
如题：如何在乱序数组中寻找最大值和最小值，要求比较次数尽可能小。
思路：如果是单纯的遍历一边，会对每一个元素与存储的最大值和最小值进行比较，比较次数为2n，
考虑到如果比最大的元素大，也就不用跟最小的元素进行对比了，比较次数会略小于2n。
显然这种思路过于常规，一般面试官也不会希望得到这种答案。
正确的思路是类似于快速排序的分组方式，
对数组从两头进行分组，即第0个元素与第n-1个元素进行对比，
大的放a组，小的放b组；然后第一个与n-2进行对比
........直到两边序号重合，比较次数为n/2，
这时，最大的数肯定在a组里，最小的数肯定在b组。然后再在a组里寻找最大值，
再在b组里寻找最小值，分别都是n/2次比较，一共使用3/2n次比较就搞定啦。
*/