如題：如何在亂序數(shù)組中尋找最大值和最小值逊谋，要求比較次數(shù)盡可能小取刃。
思路：如果是單純的遍歷一邊吧彪，會(huì)對(duì)每一個(gè)元素與存儲(chǔ)的最大值和最小值進(jìn)行比較待侵，比較次數(shù)為2n，考慮到如果比最大的元素大姨裸，也就不用跟最小的元素進(jìn)行對(duì)比了秧倾，比較次數(shù)會(huì)略小于2n。
顯然這種思路過(guò)于常規(guī)傀缩，一般面試官也不會(huì)希望得到這種答案那先。
正確的思路是類似于快速排序的分組方式，對(duì)數(shù)組從兩頭進(jìn)行分組赡艰，即第0個(gè)元素與第n-1個(gè)元素進(jìn)行對(duì)比售淡，大的放a組，小的放b組；然后第一個(gè)與n-2進(jìn)行對(duì)比........直到兩邊序號(hào)重合揖闸，比較次數(shù)為n/2揍堕，這時(shí)，最大的數(shù)肯定在a組里汤纸，最小的數(shù)肯定在b組衩茸。然后再在a組里尋找最大值，再在b組里尋找最小值贮泞，分別都是n/2次比較递瑰，一共使用3/2n次比較就搞定啦。
上代碼：
void findMaxandMinNumber(int nums[], int count) {
//分組
int i = 0;
for (; i < (count - i - 1); i++) {
if (nums[i]<nums[count-1-i]) {
//交換位置
int tem = nums[i];
nums[i] = nums[count-i-1];
nums[count-i-1] = tem;
}
}
int sep = 0;
int middle = 0;
if (i == count-i-1) {
//奇數(shù)
sep = count/2+1;
middle = nums[count/2];
} else {
//偶數(shù)
sep = count/2;
}
//大的一組
int max = nums[0];
for (int j=1; j<count/2-1; j++) {
if (nums[j]>max) {
max = nums[j];
}
}
//小的一組
int min = nums[sep];
for (int j=sep+1; j<count-1; j++) {
if (nums[j]<min) {
min = nums[j];
}
}
//與middle進(jìn)行對(duì)比
if (i == count-i-1) {
if (middle>max) {
max = middle;
}
if (middle<min) {
min = middle;
}
}
printf("max = %d, min = %d", max, min);
}
