题目描述

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题的时间复杂度要求是O(logn), 所以顺序遍历是无法通过的。解法应该是使用二分查找。

but?二分查找不是适用于顺序数组吗？这说明你还没有理解二分查找的根本思想。你还在第一层哈(～￣▽￣)～

注意：这道题是 顺序数组旋转之后的。关键词：顺序，旋转。

首先得定义两个指针

1
int left = 0,right = nums.length-1;

然后进入循环

1
while (left<right)//注意不是while (left<=right)哦，这是二分查找另一种写法

二分查找另一种写法【<—-点这可以学习二分查找另一种写法q(≧▽≦q)】

关于【left,right】区间有两种情况：

  1. 区间是有序的

    1
    if(nums[right]>=nums[left])return nums[left];

    1

  2. 区间是无序的

    旋转之后的数组，以mid为中点。肯定有一侧是有序的，一侧是无序的。

    2

    然后最小值一直在无序的一侧,不信你就找几个例子试试。

    所以我们要在无序的一侧找最小值。

    先判断左侧是不是有序的，如果有序则下一步的区间应该是右侧区间，否则就是左侧

    1
    2
    if(nums[mid]>=nums[left])left = mid+1;
    else right = mid;

    为啥 right = mid而不是 right = mid -1?

    首先是因为 while (left<right)

    还有是因为有一种情况是：nums[mid] 实际是最小值。

    !

所以需要 right = mid来包住它，这也是为什么要用while (left<right)。

你可以这么认为

  • while (left<right) 和 right = mid是一套
  • while (left<=right) 和 right = mid-1是一套

总结

循环过程中会遇见三种情况：

  • 在【left,right】内是顺序的，比如[2,5,6,7,8,9]
  • 在【left,right】内是无序的，但nums[mid]不是最小值，最小值在【left,mid】或【mid,right】中，比如[4,5,6,1,2]
  • 在【left,right】内是无序的，nums[mid]是最小值，比如[4,5,1,2,3]

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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)/2;
            if(nums[right]>=nums[left])return nums[left];
            else if(nums[mid]>=nums[left])left = mid+1;
            else right = mid;
        }
        return nums[left];
    }
}

有什么问题欢迎评论区留言！！！(´▽`ʃ♡ƪ)

__END__