1. 前言
本文的一些图片, 资料 截取自编程之美
2. 问题描述
3. 问题分析
对于这个问题, 我们最常规的思路, 就是 :
解法一 : 就是遍历一次数组, 如果当前元素, 比max大, 或者比min小, 则记录下其值, 通过这样依次遍历, 即找出了数组的最大值和最小值, 这样比较了 (2 * n)次
解法二 : 首先遍历一次数组, 两个相邻的数一组[(0, 1), (2, 3), … ], 将较小者放在左边， 较大者放在右边, 然后min在每一组的左边之中比较, max在每一组的右边之中比较, 如果数组中元素个数为奇数, 则对最后一个元素特殊处理, 最后遍历结果即为所求, 而这样只比较了 (1.5 * n)次, 优化了一些
解法三 : 这个思路和上面是一致的, 不过这里不需要改变原数组的值, 同样两个一组, 保存较小值, 和较大值, 然后小的和min比较, 大的和max比较, 如果数组中元素个数为奇数, 则对最后一个元素特殊处理, 最后遍历结果即为所求
解法四 : 分治思想, 分而制之, 如果, 求解的空间只有一个元素, 则将最大值和最小值均设置为该值 返回, 如果求解的空间有两个元素, 则比较一次, 然后设置较大值和较小值 返回, 这两个条件作为递归结束条件
然后对于 求解空间大于2个元素的情况, 将整个区间分解为两个区间, 递归求解出左边区间的最大值和最小值, 然后递归求解出右边区间的最大值和最小值, 最后合并, 结合左右两边区间的最大值和最小值, 计算出整个区间的最大值和最小值, 求的的结果即为所求
4. 代码
/**
* file name : Test16FindMaxAndMin.java
* created at : 2:50:14 PM May 23, 2015
* created by 970655147
*/
package com.hx.test03;
public class Test17FindMaxAndMin {
// 寻找最大最小元素
public static void main(String []args) {
int[] intArr = {47, 91, 18, 63, 25, 44, 86, 69, 97, 74, 15, 54, 91, 66, 52, 13, 67, 3, 67, 43, 6, 94, 65, 77, 7, 81, 30, 6, 99, 64 };
findMaxAndMin01(intArr);
findMaxAndMin02(intArr);
findMaxAndMin03(intArr);
findMaxAndMin04(intArr);
}
// 遍历一次arr 分别求min, max
public static void findMaxAndMin01(int[] arr) {
int max, min;
max = min = arr[0];
for(int i=1; i<arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
if(arr[i] < min) {
min = arr[i];
}
}
Log.log(min, max);
}
// 预处理arr 将arr以奇偶索引 分为两组 奇数存放较小者 偶数存放较大者
// 在分别在奇数组 求min, 偶数组求max
// 如果数组长度为奇数 则进行最后一个元素的判断
public static void findMaxAndMin02(int[] arr) {
int lastIdx = arr.length - 1;
for(int i=0; i<lastIdx; i+=2) {
if(arr[i] > arr[i + 1]) {
Tools.swap(arr, i, i+1);
}
}
int max = arr[1], min = arr[0];
for(int i=2; i<lastIdx; i+=2) {
if(arr[i] < min) {
min = arr[i];
}
if(arr[i+1] > max) {
max = arr[i+1];
}
}
if((arr.length & 1) == 1) {
if(arr[lastIdx] < min) {
min = arr[lastIdx];
}
if(arr[lastIdx] > max) {
max = arr[lastIdx];
}
}
Log.log(min, max);
}
// 对arr 两个一组进行遍历
// 去较大者和max进行比较 去较小者和min进行比较
// 如果数组长度为奇数 则进行最后一个元素的判断
// 这种方法 不会修改原来的数组
public static void findMaxAndMin03(int[] arr) {
int lastIdx = arr.length - 1;
int max = arr[0], min = arr[0];
int tmp01, tmp02;
for(int i=0; i<lastIdx; i+=2) {
if(arr[i] > arr[i + 1]) {
tmp01 = arr[i];
tmp02 = arr[i+1];
} else {
tmp01 = arr[i+1];
tmp02 = arr[i];
}
if(tmp01 > max) {
max = tmp01;
}
if(tmp02 < min) {
min = tmp02;
}
}
if((arr.length & 1) == 1) {
if(arr[lastIdx] < min) {
min = arr[lastIdx];
}
if(arr[lastIdx] > max) {
max = arr[lastIdx];
}
}
Log.log(min, max);
}
// 分而制之
public static void findMaxAndMin04(int[] arr) {
int[] res = findMaxAndMin040(arr, 0, arr.length-1);
Log.log( res[1], res[0]);
}
// low, high 包括low, high
// 如果low==high 则说明需要findMaxAndMin040的只有一个数字 则令res[0], res[1]均为该数 然后返回
// 否则 如果(low+1)==high 则说明只有两个数字 则令res[0]为较大者, res[1]为较小者
// 否则 对low, high在分成两部分 递归调用findMaxAndMin040 在左半边的结果和右半边的结果中取min, max
private static int[] findMaxAndMin040(int[] arr, int low, int high) {
int[] res = new int[2];
if(low == high) {
res[0] = res[1] = arr[low];
return res;
} else if((low + 1) == high) {
if(arr[low] > arr[low+1]) {
res[0] = arr[low];
res[1] = arr[low+1];
} else {
res[0] = arr[low+1];
res[1] = arr[low];
}
return res;
}
int len = high - low;
int[] tmp01, tmp02;
if((len & 1) == 1) {
int mid = low + len / 2;
tmp01 = findMaxAndMin040(arr, low, mid);
tmp02 = findMaxAndMin040(arr, mid, high);
} else {
int mid = low + len / 2;
tmp01 = findMaxAndMin040(arr, low, mid);
tmp02 = findMaxAndMin040(arr, mid+1, high);
}
res[0] = (tmp01[0] > tmp02[0]) ? tmp01[0] : tmp02[0];
res[1] = (tmp01[1] < tmp02[1]) ? tmp01[1] : tmp02[1];
return res;
}
}
5. 运行结果
6. 总结
通常, 对于我来说, 我可能只会使用第一种方法, 哈哈 毕竟太难想了, 但是那些专研算法的大神们, 总是会给我们惊喜, 想到更优的解法, 然后分享出来, 感谢这种思想 free
注 : 因为作者的水平有限，必然可能出现一些bug, 所以请大家指出！