本文共 1400 字,大约阅读时间需要 4 分钟。
class Solution { public int minArray(int[] numbers) { for(int i = 0; i < numbers.length-1; i++) { if(numbers[i] > numbers[i+1]) return numbers[i+1]; } return numbers[0]; }}
二分法:
时间复杂度O(logn),最差的时候为O(n) 声明 i, j 双指针分别指向 numbers 数组左右两端;m为i,j中点,当i<j时,判断 numbers[m]和numbers[j]的大小。分三种情况: if(numbers[m] < numbers[j]) //说明m在右排序数组中,旋转点在左边 j = m; else if(numbers[m] > numbers[j]) //说明m在左排序数组中,旋转点在右边 i = m + 1; //旋转点一定会在右排序数组中,所以i=m+1,免得多比较一个数 else if(numbers[m] == numbers[j]) //无法判断m在哪个数组中 j = j - 1; 第三种情况可能会错过旋转点,但是还是能返回与旋转点值相同的点 代码:class Solution { public int minArray(int[] numbers) { int i,j,m; i = 0; j = numbers.length-1; m = (i + j) / 2; while(i < j) { if(numbers[m] < numbers[j]) //说明m在右排序数组中,旋转点在左边 j = m; else if(numbers[m] > numbers[j]) //说明m在左排序数组中,旋转点在右边 i = m + 1; else if(numbers[m] == numbers[j]) //无法判断m在哪个数组中 j = j - 1; m = (i + j) / 2; } return numbers[i]; }}
之前没有深刻理解当nums[j] == nums[mid]时,为什么j–一定是正确的。二刷时甚至忘记了当nums[j] == nums[mid]时,无法判断旋转点在哪一边。比如:3,3,3,3,3,4,5,3,3这个数组,第一次nums[mid] = 3,nums[j] = 3, 此时无法判断旋转点位置,j–,nums[mid] = 3,j会一直减到i的位置停下,返回nums[i],此时nums[i]虽然不是旋转点,但是与旋转点的值一定相同,因为左右都是递增序列。
这里总结一下:
1、左闭右闭区间,i = m + 1,j = m - 1,当i>j的时候停止. 2、左闭右开区间,i = m + 1, j = m,当i = j 的时候停止转载地址:http://grim.baihongyu.com/