Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class {
public int findMin(int[] nums) {
int start = 0;
int end = nums.length-1;
while(start < end){
int mid = start + ((end - start)>>1);
if(nums[mid] > nums[end]){
start = mid + 1;
}
else
end = mid;
}
return nums[start];
}
}
|
- 每次和最后一个元素比较。
- 1 2 3 -> s 1, e 3, m 2 -> s 1, e 1
- 3 2 1 -> s 3, e 1, m 2 -> s 2, e 1 -> s 2 e 1 m 2 -> s 1 e 1
what if there is duplicate items,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class {
public int findMin(int[] nums) {
int start = 0;
int end = nums.length-1;
while(start < end){
int mid = start + ((end - start)>>1);
if(nums[mid] > nums[end]){
start = mid + 1;
}
else if(nums[mid] < nums[end])
end = mid;
else
end --;
}
return nums[start];
}
}
|
- example: 3, 3, 1, 3
- 当出现这种情况时，mid == end, 需要end–
近期评论