这道题表面上是一个简单的数组排序输出最小值的问题,但考虑到旋转数组的部分有序性,可以简化查找最小值的过程。
如我选择从数组末尾开始查找,由于旋转,数组末端旋转后的部分从尾部遍历是递减的,当num[i]<num[i-1]时,找到旋转前数组第一个元素,即最小值。
代码如下:
class Solution { public int minArray(int[] numbers) { for(int i = numbers.length-1; i>0; i--) { if (numbers[i] < numbers[i-1]) return numbers[i]; } return numbers[0]; } }
时间复杂度为O(n),空间复杂度为O(1)
官方提供的题解是二分法,同样利用了旋转数组的部分有序性特点。
在二分查找的每一步中,左边界为low,右边界为high,区间的中点为pivot
当num[pivot]<num[high]时,pivot在最小值右侧,忽略右半部分;
当num[pivot]>num[high]时,pivot在最小值左侧,忽略左半部分;
当num[pivot]=num[high]时,由于重复元素的存在,我们并不能确定num[pivot] 究竟在最小值的左侧还是右侧,
由于它们的值相同,所以无论num[high] 是不是最小值,都有一个它的「替代品」numbers[pivot],因此我们可以忽略二分查找区间的右端点。
代码如下:
class Solution { public int minArray(int[] numbers) { int low = 0; int high = numbers.length - 1; while (low < high) { int pivot = low + (high - low) / 2; if (numbers[pivot] < numbers[high]) { high = pivot; } else if (numbers[pivot] > numbers[high]) { low = pivot + 1; } else { high -= 1; } } return numbers[low]; } } 作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-by-leetcode-s/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。