Poison

154. Find Minimum in Rotated Sorted Array II

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] < nums[right]) {
                // [numbers[mid] ... numbers[right] 递增，说明 numbers[mid] 可能为最小元素，且 numbers[right] 不可能为最小元素
                right = mid;
            } else if (nums[mid] > nums[right]) {
                // numbers[mid] 不可能为最小元素
                left = mid + 1;
            } else {
                // 两个元素值相同，无法判断继续在左侧搜索还是右侧搜索，丢弃最右侧元素
                right--;
            }
        }

        return nums[left]; // 注意题目要求返回元素而不是索引
    }
}

关键点在于与右端元素相比较，且可能存在重复元素。该题要求返回元素值，未要求返回元素索引，所以遇到重复值时可以直接跳过。

Reference

154. Find Minimum in Rotated Sorted Array II
剑指 Offer 11. 旋转数组的最小数字