数组是最简单的一种数据结构。我们经常碰到一个基本的问题,就是寻找整个数组中的最大数或最小数。我们只需
遍历一遍数组,就能找到最大(最小)数。如果同时寻找最大数和最小数呢?对于一个由N个整数组成的数组,需要比较多少次才能把最大和最小的数找出来呢?
解法一:
可以把这个问题分解为两个问题,求最大值和最小值,我们可以遍历两边数组,第一遍求最大值,第二遍求最小值,时间复杂度为O(2*N)。
解法二:
我们可以在概念上把数组中相邻的两个元素分为一组,然后比较这两个元素,较大者和max比较,如果大于max则更新max,较小者和min比较,小于min则更新min。算法的时间复杂度为O(1.5*n)。例如:
实现代码:
void find_max_min(int *a, int length, int *max, int *min) { if (length <= 0) return; if (length <= 1) { *max = *min = a[length-1]; return; } /*初始化max和min*/ *max = a[0] > a[1] ? a[0] : a[1]; *min = a[0] > a[1] ? a[1] : a[0]; int i; int n; if (length % 2) n = length - 1; else n = length; for (i = 2; i < n;i+=2) { if (a[i] > a[i+1]) { *max = *max > a[i] ? *max : a[i]; *min = *min > a[i + 1] ? a[i + 1] : *min; } else { *max = *max > a[i+1] ? *max : a[i+1]; *min = *min > a[i] ? a[i] : *min; } } /*如果length为奇数,则剩下最后一个元素没有做过比较*/ if (i < length) { *max = *max > a[i] ? *max : a[i]; *min = *min > a[i] ? a[i] : *min; } }解法三:
分治思想是解决问题常用的一种技巧。我们可以先求出前n/2个数的max和min,然后求出后n/2个数的max和min,取较大的max和较小的min即可。算法时间复杂度为O(1.5*n)。
void find_max_min(int *a, int satrt, int end,int *max, int *min) { if (end >= satrt) { if (end - satrt <= 1) { if (a[end] > a[satrt]) { *max = a[end]; *min = a[satrt]; } else { *max = a[satrt]; *min = a[end]; } return; } int left_max, left_min, right_max, right_min; int mid = (satrt + end) / 2; find_max_min(a, satrt, mid, &left_max, &left_min); find_max_min(a, mid + 1, end, &right_max, &right_min); *max = left_max > right_max ? left_max : right_max; *min = left_min > right_min ? right_min : left_min; } }