来源Leetcode第154题寻找旋转数组中的最小值II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
二分查找
思路同上一题153，只是在判断相等时直接舍弃即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int findMin(int[] nums) {
int left=0,right=nums.length-1;
while (left <= right && nums[left] >= nums[right]) {
int mid = (left+right) >>> 1;
if (nums[mid] > nums[right]){
left = mid+1;
} else if (nums[mid] < nums[right]){
right = mid;
}
else
right--;
}
return nums[left];
}
|
去重
可以做一个预处理，保证所有重复数字不在两段里出现即可，再简单化，也就是保证切割的位置不要是重复数字。也就是比较 start 和 end 是否相同，相同的话 end-- 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int findMin(int[] nums) {
int start = 0;
int end = nums.length - 1;
while (nums[end] == nums[start] && end > start) {
end--;
}
while (start < end) {
int mid = (start + end) >>> 1;
if (nums[mid] > nums[end]) {
start = mid + 1;
} else{
end = mid;
}
}
return nums[start];
}
|