153. Find Minimum in Rotated Sorted Array

题目描述和难度

• 题目描述：

输入: [3,4,5,1,2]
输出: 1

输入: [4,5,6,7,0,1,2]
输出: 0

• 题目难度：中等。
• 英文网址：153. Find Minimum in Rotated Sorted Array 。
• 中文网址：153. 寻找旋转排序数组中的最小值 。

思路分析

求解关键：这道题“你可以假设数组中不存在重复元素”这个信息是关键的。

参考解答

参考解答1：二分查找算法。

public class Solution {

    public int findMin(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            throw new IllegalArgumentException("数组为空");
        }
        int left = 0;
        int right = len - 1;
        // 思考，为什么是 left < right
        while (left < right) {
            // 这一步就是取中点，没有什么特别之处
            int mid = left + (right - left) / 2;

            // 特别注意：这里有个大坑，不能用 nums[left] < nums[mid]
            // 特别注意：这里有个大坑，不能用 nums[left] < nums[mid]
            // 特别注意：这里有个大坑，不能用 nums[left] < nums[mid]

            if (nums[mid] > nums[right]) {
                // 5 6 7 8 9 1 2
                // 此时可以扔掉 mid 的值
                left = mid + 1;
            } else {
                // 5 6 7 1 2 3 4
                assert nums[mid] < nums[right];
                // 此时 mid 有可能是最小值所在的索引
                right = mid;
            }
        }

        // 退出循环说明 left 与 right 相等，所以只剩一个元素可能，
        // 所以 return [left] 或者 return [right] 都可以了
        // 注意不能 return mid，可以从 {2,1} 这个输入看出来。

        return nums[right];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int min = solution.findMin(nums);
        System.out.println(min);
    }
}

参考解答2：使用分治的思想

/**
 * 分治的写法
 */
public class Solution2 {

    // 虽然可以通过，但是时间复杂度是 O(n)

    public int findMin(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            throw new IllegalArgumentException("数组为空");
        }
        return findMin(nums, 0, len - 1);
    }

    private int findMin(int[] nums, int left, int right) {
        // 思考：这个临界条件是为什么?
        // 或者写成 left + 1 >= right
        if (left == right || left + 1 == right) {
            return Math.min(nums[left], nums[right]);
        }
        int mid = left + (right - left) / 2;
        // 8 9 1 2 3 4 5 6 7
        if (nums[mid] < nums[right]) {
            // 右边是顺序数组
            return Math.min(findMin(nums, left, mid - 1), nums[mid]);
        } else {
            // 左边是顺序数组
            // nums[mid] > nums[right]
            // 3 4 5 6 7 8 1 2
            return Math.min(nums[left], findMin(nums, mid + 1, right));
        }
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[] nums = {1, 2};
        int solution2Min = solution2.findMin(nums);
        System.out.println(solution2Min);
    }

}

参考解答3：使用分治的思想

public class Solution3 {

    public int findMin(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            throw new IllegalArgumentException("给出的数组为空，没有最小值");
        }
        return findMin(nums, 0, len - 1);
    }

    public int findMin(int[] nums, int left, int right) {
        // 分治的方法，首先先要处理要递归终止的条件
        if (left + 1 >= right) {
            return Math.min(nums[left], nums[right]);
        }
        if (nums[left] < nums[right]) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        return Math.min(findMin(nums, left, mid), findMin(nums, mid + 1, right));
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0153-find-minimum-in-rotated-sorted-array ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。