leetcode 152&153 Find Minimum in Rotated Sorted Array
z
 2018-03-08 22:12:26  

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 Solution {
    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 Solution {
    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–