1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findMin(int[] nums) {
        if (nums[nums.length - 1] >= nums[0])
            return nums[0];
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[0]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

就是和那个找某个数字在sorted array中是否存在的那道题一样. 模板是一样的. 就是left是小于right而不是小于等于, 遇到nums[mid] < nums[0]这个数字可能是最小值但不一定, 我们此时要接着往左找, 于是让right = mid, 意思就是让mid的位置依旧在我们找的范围之中. 如果遇到nums[mid] > nums[0], 这说明mid这个数字一定不是答案, 我们排除他然后往右找. 很简单.

时间复杂度: O(logn)
空间复杂度: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findMin(int[] nums) {
        if (nums[0] <= nums[nums.length - 1]) {
            return nums[0];
        }
        int left = 0, right = nums.length - 1, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= nums[0]) {
                left = mid + 1;
            } else {
                ans = nums[mid];
                right = mid - 1;
            }
        }
        return ans;
    }
}

后来又自己写的一版答案. 这个就是按照我的模板严格去写的. 首先判断是不是rotated了, 也就是开始的判断. 如果不是直接返回nums[0]即可. 注意此时我们的条件是小于等于而不是小于, 这是考虑到nums只有一个元素的情况, 这时第0个和最后一个元素是同一个元素.

然后如果确实rotated了, 我们就开始找. 如果此时nums[mid]大于nums[0], 那说明mid在数字较大的那一部分也就是在rotated后的数组前一部分. 此时不是答案, 我们让left = mid + 1. 如果nums[mid] < nums[0], 这说明mid在rotated的array后半部分, 此时可能是答案但不确定, 于是让ans = nums[mid], 继续往左找看有没有更好的. 如果nums[mid] == nums[0]也就是此时范围的中点是nums[0], 那么一样的nums[0]也在rotated的数组前半部分, 我们要往右找, 于是left = mid + 1. 综合就是如果mid出现在前一部分数组, 那么它肯定不是答案, 我们往右找; 如果出现在rotated的数组后一部分, 那么此时mid指向的可能是答案, 但不确定, 于是我们接着往左找.

时间复杂度: O(logn)
空间复杂度: O(1)