本文共 1529 字,大约阅读时间需要 5 分钟。
这个博客不错,要关注下~
问题:
一个int数组, 比如 array[],里面数据无任何限制,要求求出所有这样的数array[i],其左边的数都小于等于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。
分析:
最原始的方法是检查每一个数 array[i] ,看是否左边的数都小于等于它,右边的数都大于等于它。这样做的话,要找出所有这样的数,时间复杂度为O(N^2)。
其实可以有更简单的方法,我们使用额外数组,比如rightMin[],来帮我们记录原始数组array[i]右边(包括自己)的最小值。假如原始数组为: array[] = {7, 10, 2, 6, 19, 22, 32}, 那么rightMin[] = {2, 2, 2, 6, 19, 22, 32}. 也就是说,7右边的最小值为2, 2右边的最小值也是2。
有了这样一个额外数组,当我们从头开始遍历原始数组时,我们保存一个当前最大值 max, 如果当前最大值刚好等于rightMin[i], 那么这个最大值一定满足条件。还是刚才的例子。
第一个值是7,最大值也是7,因为7 不等于 2, 继续,
第二个值是10,最大值变成了10,但是10也不等于2,继续,
第三个值是2,最大值是10,但是10也不等于2,继续,
第四个值是6,最大值是10,但是10不等于6,继续,
第五个值是19,最大值变成了19,而且19也等于当前rightMin[4] = 19, 所以,满足条件。
如此继续下去,后面的几个都满足。
设array[i]是满足条件的数,则从0-i的最大得数是array[i], 从i-n-1最小的数是array[i],所有要找一个最大值等于最小值的数
/** * @author beiyeqingteng * @link http://blog.csdn.net/beiyeqingteng */public static void smallLarge(int[] array) throws Exception{ //the array's size must be larger than 2 if (array == null || array.length < 1) { throw new Exception("the array is null or the array has no element!"); } int[] rightMin = new int[array.length]; rightMin[array.length - 1] = array[array.length - 1]; //get the minimum value of the array[] from i to array.length - 1 for (int i = array.length - 2; i >= 0; i--) { if (array[i] < rightMin[i + 1]) { rightMin[i] = array[i]; } else { rightMin[i] = rightMin[i + 1]; } } int leftMax = Integer.MIN_VALUE; for (int i = 0; i < array.length; i++) { if (leftMax <= array[i]) { leftMax = array[i]; if (leftMax == rightMin[i]) { System.out.println(leftMax); } } }}