题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
案例
{3 4 5 1 2} (一般情况) {1 2 3 4 5} (特例,前面0个元素搬到后面,即已经排好序的情况) {1 0 1 1 1} / {1 1 1 0 1}(特例,都可以看成递增排序数组{0 1 1 1 1 }的旋转)
分析
遍历整个数组找出其中最小的数,复杂度为O(n),这是最容易想到的方案,但这样没用到旋转数组的特性,肯定不行!!
本题考查二分查找。旋转之后的数组实际上可以划分成两个有序的子数组:前面子数组的元素都大于后面子数组中的元素,而且最小的元素刚好是这两个子数组的分界线。
- 和二分查找一样,用两个指针分别指向数组的第一个元素和最后一个元素。
- 找到数组的中间元素,如果中间元素大于第一个指针指向的元素,则中间元素位于前面的递增子数组,此时最小元素位于中间元素的后面,我们让第一个指针left指向该中间元素;如果中间元素小于第二个指针指向的元素,则中间元素位于后面的递增子数组,此时最小元素位于中间元素的前面,我们让第二个指针right指向中间元素。
- 这样查找范围会缩小到原来的一半,第一个指针总是指向前面递增数组的元素,第二个指针总是指向后面的递增数组的元素。最终,第一个指针将指向前面子数组的最后一个元素,而第二个指针会指向后面子数组的第一个元素(也就是最小的元素),即它们最终指向两个相邻的元素,循环结束。
☆☆☆☆解法
class Solution { public int minNumberInRotateArray(int[] nums) { if (nums == null || nums.length == 0) return 0; int l = 0, r = nums.length - 1; while (l < r) { int mid = l + (r - l) / 2; // 如果数组元素允许重复,会出现一个特殊的情况: // nums[l] == nums[m] == nums[h], // 此时无法确定解在哪个区间,需要切换到顺序查找。 // 例如对于数组 {1,1,1,0,1},l、m 和 h 指向的数都为 1, // 此时无法知道最小数字 0 在哪个区间。 if (nums[mid] == nums[l] && nums[mid] == nums[r]) { return minNumber(nums, l, r); } // 这里要跟右边界r 比,因为当只有两个数时(a,b) // 那么mid肯定取l.当判断条件l与mid比时,会出现与自身比情况 不好判断 // 例如 (1,3) 和 (3,1) if (nums[mid] <= nums[r]) { r = mid; }else { l = mid + 1; } } return nums[l]; } private int minNumber(int[] nums, int l, int r) { int min = nums[l]; for (int i = l + 1; i <= r; i++) { if (nums[i] < min) { min = nums[i]; } } return min; } }
Note:
关于取中间值为什么是left+(right-left)/2,而不是直接(right+left)/2?
答:第一种方式更稳定!!如果两个数都很大,相加将导致溢出。
int x = 1999999998; int y = 1999999998; int mid = (x+y) / 2; int mid2 = x + (y-x) / 2; System.out.println(mid); //-147483650 System.out.println(mid2); //1999999998