题解 | #旋转数组的最小数字#

题目的主要信息：

• 有一个长度为 n 的非降序数组，把一个数组最开始的若干个元素“平移”到数组的末尾，变成一个旋转数组
• 找到这个旋转数组的最小值

举一反三：

学习完本题的思路你可以解决如下题目：

BM17.二分查找-I

BM18.二维数组中的查找

BM19.寻找峰值

方法一：二分法（推荐使用）

知识点：分治

分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

思路：

旋转数组将原本有序的数组分成了两部分有序的数组，因为在原始有序数组中，最小的元素一定是在首位，旋转后无序的点就是最小的数字。我们可以将旋转前的前半段命名为A，旋转后的前半段命名为B，旋转数组即将AB变成了BA，我们想知道最小的元素到底在哪里。

因为A部分和B部分都是各自有序的，所以我们还是想用分治来试试，每次比较中间值，确认目标值（最小元素）所在的区间。

具体做法：

• step 1：双指针指向旋转后数组的首尾，作为区间端点。
• step 2：若是区间中点值大于区间右界值，则最小的数字一定在中点右边。
• step 3：若是区间中点值等于区间右界值，则是不容易分辨最小数字在哪半个区间，比如[1,1,1,0,1]，应该逐个缩减右界。
• step 4：若是区间中点值小于区间右界值，则最小的数字一定在中点左边。
• step 5：通过调整区间最后即可锁定最小值所在。

图示：

Java实现代码：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            //最小的数字在mid右边
            if(array[mid] > array[right]) 
                left = mid + 1;
            //无法判断，一个一个试
            else if(array[mid] == array[right]) 
                right--;
            //最小数字要么是mid要么在mid左边
            else 
                right = mid;
        }
        return array[left];
    }
}

C++实现代码：

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0;
        int right = rotateArray.size() - 1;
        while(left < right){
            int mid = (left + right) / 2;
            //最小的数字在mid右边
            if(rotateArray[mid] > rotateArray[right]) 
                left = mid + 1;
            //无法判断，一个一个试
            else if(rotateArray[mid] == rotateArray[right]) 
                right--;
            //最小数字要么是mid要么在mid左边
            else 
                right = mid;
        }
        return rotateArray[left];
    }
};

Python实现代码

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        left = 0
        right = len(rotateArray) - 1
        while left < right:
            mid = int((left + right) / 2) 
            #最小的数字在mid右边
            if rotateArray[mid] > rotateArray[right]: 
                left = mid + 1 
            #无法判断，一个一个试
            elif rotateArray[mid] == rotateArray[right]: 
                right -= 1
            #最小数字要么是mid要么在mid左边
            else:
                right = mid 
        return rotateArray[left]

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，二分法最坏情况对$nn$取2的对数
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间

方法二：遍历查找（扩展思路）

思路：

再怎么旋转，这也是一个数组，我们要找的数组最小值。更通用的解法莫过于遍历数组，维护最小值。

具体做法：

• step 1：因为数组长度不小于1，因此最初的最小值可以设置为数组首元素或者int型最大值。
• step 2：从左到右遍历整个数组，依次检查当前元素与记录元素的大小，若是当前元素更小，则记录最小的元素更新。
• step 3：遍历结束，最终记录的最小值即是所求。

Java实现代码：

import java.util.*;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        //数组一定有元素
        int res = array[0]; 
        //遍历数组
        for(int i = 1; i < array.length; i++) 
            //每次维护最小值
            res = Math.min(res, array[i]); 
        return res;
    }
}

C++实现代码：

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int res = INT_MAX;
        //遍历数组
        for(int i = 0; i < rotateArray.size(); i++) 
            //每次维护最小值
            res = min(res, rotateArray[i]); 
        return res;
    }
};

Python实现代码

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # 数组一定有元素
        res = rotateArray[0] 
        # 遍历数组
        for i in range(len(rotateArray)): 
            # 每次维护最小值
            res = min([res, rotateArray[i]]) 
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为数组大小，遍历一次数组
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间