53 lines
1.5 KiB
C++
53 lines
1.5 KiB
C++
#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次比较就搞定啦。
|
||
*/
|
||
|