首页 > 试题广场 >

旋转数组的最小数字

[编程题]旋转数组的最小数字
  • 热度指数：1386572 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：，数组中任意元素的值: 
要求：空间复杂度： ，时间复杂度：
示例1

输入

[3,4,5,1,2]

输出

1
示例2

输入

[3,100,200,3]

输出

3
算法知识视频讲解
查看答案及解析
添加回答
推荐
念润头像 念润
思路

剑指Offer中有这道题目的分析。这是一道二分查找的变形的题目。


旋转之后的数组实际上可以划分成两个有序的子数组：前面子数组的大小都大于后面子数组中的元素

注意到实际上最小的元素就是两个子数组的分界线。本题目给出的数组一定程度上是排序的，因此我们试着用二分查找法寻找这个最小的元素。

思路：

（1）我们用两个指针left,right分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则，第一个元素应该是大于最后一个元素的（没有重复的元素）。

但是如果不是旋转，第一个元素肯定小于最后一个元素。

（2）找到数组的中间元素。

中间元素大于第一个元素，则中间元素位于前面的递增子数组，此时最小元素位于中间元素的后面。我们可以让第一个指针left指向中间元素。

移动之后，第一个指针仍然位于前面的递增数组中。

中间元素小于第一个元素，则中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面。我们可以让第二个指针right指向中间元素。

移动之后，第二个指针仍然位于后面的递增数组中。

这样可以缩小寻找的范围。

（3）按照以上思路，第一个指针left总是指向前面递增数组的元素，第二个指针right总是指向后面递增的数组元素。

最终第一个指针将指向前面数组的最后一个元素，第二个指针指向后面数组中的第一个元素。

也就是说他们将指向两个相邻的元素，而第二个指针指向的刚好是最小的元素，这就是循环的结束条件。

到目前为止以上思路很耗的解决了没有重复数字的情况，这一道题目添加上了这一要求，有了重复数字。

因此这一道题目比上一道题目多了些特殊情况：

我们看一组例子：｛1，0，1，1，1｝ 和 ｛1，1， 1，0，1｝ 都可以看成是递增排序数组｛0，1，1，1，1｝的旋转。

这种情况下我们无法继续用上一道题目的解法，去解决这道题目。因为在这两个数组中，第一个数字，最后一个数字，中间数字都是1。

第一种情况下，中间数字位于后面的子数组，第二种情况，中间数字位于前面的子数组。

因此当两个指针指向的数字和中间数字相同的时候，我们无法确定中间数字1是属于前面的子数组（绿色表示）还是属于后面的子数组（紫色表示）。

也就无法移动指针来缩小查找的范围。

代码 
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int size = rotateArray.size();
        if(size == 0){
            return 0;
        }//if
        int left = 0,right = size - 1;
        int mid = 0;
        // rotateArray[left] >= rotateArray[right] 确保旋转
        while(rotateArray[left] >= rotateArray[right]){
            // 分界点
            if(right - left == 1){
                mid = right;
                break;
            }//if
            mid = left + (right - left) / 2;
            // rotateArray[left] rotateArray[right] rotateArray[mid]三者相等
            // 无法确定中间元素是属于前面还是后面的递增子数组
            // 只能顺序查找
            if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid]){
                return MinOrder(rotateArray,left,right);
            }//if
            // 中间元素位于前面的递增子数组
            // 此时最小元素位于中间元素的后面
            if(rotateArray[mid] >= rotateArray[left]){
                left = mid;
            }//if
            // 中间元素位于后面的递增子数组
            // 此时最小元素位于中间元素的前面
            else{
                right = mid;
            }//else
        }//while
        return rotateArray[mid];
    }
private:
    // 顺序寻找最小值
    int MinOrder(vector<int> &num,int left,int right){
        int result = num[left];
        for(int i = left + 1;i < right;++i){
            if(num[i] < result){
                result = num[i];
            }//if
        }//for
        return result;
    }
};

int main(){
    Solution s;
    //vector<int> num = {0,1,2,3,4,5};
    //vector<int> num = {4,5,6,7,1,2,3};
    vector<int> num = {2,2,2,2,1,2};
    int result = s.minNumberInRotateArray(num);
    // 输出
    cout<<result<<endl;
    return 0;
}
编辑于 2015-08-18 23:34:39 回复(141)
Python
木子梨丶头像 木子梨丶 
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        return (min(rotateArray))

发表于 2022-08-03 18:53:04 回复(0)
Python
HHHChen77头像 HHHChen77
python  二分 
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
        length = len(rotateArray)
        # 二分查找
        left = 0
        right = length - 1
        while left < right:
            mid = left + (right - left) // 2
            if rotateArray[mid] < rotateArray[right]:
                right = mid
            elif rotateArray[mid] > rotateArray[right]:
                left = mid + 1
            # 无法确认就缩小1
            else:
                right -= 1
         # 返回最小值
        return rotateArray[left]
发表于 2021-08-25 19:43:15 回复(0)
Python
牛客76226381号头像 牛客76226381号
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        left=0
        right=len(rotateArray)-1
        while left<=right:
            mid=left+right >> 1
            if rotateArray[mid]<rotateArray[mid-1]:
                return rotateArray[mid]
            elif rotateArray[mid]>rotateArray[mid+1]:
                return rotateArray[mid+1]
            elif rotateArray[mid]<=rotateArray[right]:
                right= mid -1
            else:
                left=mid+1
        return 0
笨方法 非递减的，多判断一步是mid+1
发表于 2021-08-15 20:50:47 回复(0)
Python
wengJJ头像 wengJJ
Python
利用了数组原本已排序的特点 
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
#        面试滚粗代码
#         return min(rotateArray)
#                正经代码
        if not rotateArray:
            return 0
        if len(rotateArray)==1:
            return rotateArray[0]
        min_num = rotateArray[0]
        for i in range(len(rotateArray)):
            if rotateArray[i] < min_num:
                min_num = rotateArray[i]
                break
        return min_num


发表于 2021-06-12 01:29:58 回复(0)
Python
vectorlery头像 vectorlery 
# python 方法
# 该题目个人理解用不到二分查找  因为二分查找的前提是有序的列表/数组，
# 既然列表/数字有序 ，那么，最小元素一定在列表/数组第一个元素或者最后一个元素
# 直接取出即可
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        rotateArray.sort()
        return rotateArray[0]


编辑于 2021-06-07 20:24:29 回复(0)
Python
lucky_forever头像 lucky_forever
题目感觉不太严谨，如果给的序列为[1,5,6,2,3,4]，用题解的二分查找将得出错误答案2。其实可以不用二分查找，因为原始数组为非递减，直接将第一个元素设为最小值，再从序列末尾与最小值进行比较，如果小于最小值则更新最小值，否则直接退出循环，这样的算法时间复杂度为O(log N) 
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if rotateArray == []:
            return 0
        elif len(rotateArray) == 1:
            return rotateArray[0]
        elif len(rotateArray) == 2:
            return min(rotateArray[0], rotateArray[1])
        else:
            i = len(rotateArray)-1
            mi = rotateArray[0]
            while i >= 0:
                if rotateArray[i] <= mi:
                    mi = rotateArray[i]
                else:
                    break
                i -= 1
            return mi
        # write code here


发表于 2021-04-27 22:04:22 回复(1)
Python
牛客541273514号头像 牛客541273514号 
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray)==0:
            return 0
        else:
            if len(rotateArray)<=2:
                return rotateArray[-1]
            else:
                head=0
                tail=len(rotateArray)-1
                while head+1 !=tail:
                    mid=(head+tail)//2
                    if rotateArray[mid]>=rotateArray[head]:
                        head=mid
                    if rotateArray[mid]<=rotateArray[tail]:
                        tail=mid
                return rotateArray[tail]
           
while True:
    try:
        s=Solution()
        array=input()
        print(s.minNumberInRotateArray(array))
    except:
        break

发表于 2021-04-12 15:05:01 回复(0)
Python
牛客771940155号头像 牛客771940155号
# -*- coding:utf-8 -*-
#二分法，截止条件：两个子区间都符合初始值小于末尾值，取两个子区间的初始值比较，返回较小的一个
#否则对初始值大于末尾值的子区间继续二分
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
        else:
            startIndex = 0
            endIndex = len(rotateArray) - 1
            while True:
                if rotateArray[startIndex] <= rotateArray[startIndex+int((endIndex-startIndex)/2)] and rotateArray[startIndex+int((endIndex-startIndex)/2)+1] <= rotateArray[endIndex]:
                    return rotateArray[startIndex] if rotateArray[startIndex] < rotateArray[startIndex+int((endIndex-startIndex)/2)+1] else rotateArray[startIndex+int((endIndex-startIndex)/2)+1]
                else:
                    if rotateArray[startIndex] <= rotateArray[startIndex+int((endIndex-startIndex)/2)]:
                        startIndex = startIndex+int((endIndex-startIndex)/2) + 1
                    else:
                        endIndex = startIndex+int((endIndex-startIndex)/2)
#注意题目中非递增数组的描述，判断时使用<=;注意缩小二分区间时起始和结束索引位置的赋值要加上原来的起始位置值
发表于 2021-04-11 10:51:10 回复(0)
Python
牛客578317901号头像 牛客578317901号 
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, alist):
        n = len(alist)
        low = 0
        high = n-1
        mid = 0
        while low < high:
            mid = (low + high) // 2
            if alist[mid] > alist[high]:
                low = mid + 1 # mid元素大于high，最小值在右边
            elif alist[mid] < alist[high]: # mid小于high，最小值在左边
                high = mid # mid小于high，先另high为mid
            else: # 00011 11000   1000  12345  51234
                low += 1
        return alist[low]

                
                
                
             
                

发表于 2021-04-05 19:00:39 回复(0)
Python
obession头像 obession
        if len(rotateArray) == 0:
            return 0
        return sorted(rotateArray, reverse=True)[-1]
发表于 2021-03-12 20:42:23 回复(0)
Python
西南交大巨可爱头像 西南交大巨可爱 
# Python使用二分法查找
class Solution:
    def minNumberInRotateArray(self, arr):
        # write code here
        if not arr: return 0
        if len(arr) == 1:
            return None
        left = 0
        right = len(arr) - 1
        while left < right:
            mid = (left + right) // 2
            if arr[mid] < arr[mid - 1]:
                return arr[mid]
            else:
                if arr[mid] > arr[0]:
                    left = mid +1
                else:
                    right = mid
        return arr[-1] #若循环结束还未找到，证明最小值为数组最后一位

发表于 2021-03-09 21:54:56 回复(0)
Python
小千北拥有offer啦！头像 小千北拥有offer啦！ 
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray)==0:
            return 0
        elif len(rotateArray)==1:
            return rotateArray[0]
        else:
            left=0
            right=len(rotateArray)-1
            while left<right:
                mid=(left+right)//2
                if rotateArray[mid]<rotateArray[right]:
                    right=mid
                elif rotateArray[mid]>rotateArray[right]:
                    left=mid+1
                else:
                    left+=1
            return rotateArray[left]

发表于 2021-02-20 00:26:45 回复(0)
Python
牛客706887890号头像 牛客706887890号 
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if rotateArray is None:
            return 0
        left = 0
        right = len(rotateArray) - 1
        while True:
            mid = (left + right)//2
            if rotateArray[mid] > rotateArray[right]:
                left = mid + 1
            elif rotateArray[mid-1] < rotateArray[mid]:
                right = mid 
            elif rotateArray[mid-1] == rotateArray[mid]:
                right -= 1
            else:
                return rotateArray[mid]


发表于 2021-01-17 18:09:34 回复(0)
Python
牛客584356146号头像 牛客584356146号
剑指offer的思路：特殊情况只能用顺序查找 
import math

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        else:
            ind1 = 0
            ind2 = len(rotateArray) - 1
            mid = ind1
            while rotateArray[ind1] >= rotateArray[ind2]:
                if ind2 - ind1 == 1:
                    mid = ind2
                    break
                else:
                    mid = math.ceil((ind1+ind2)/2)
                    if rotateArray[ind1] == rotateArray[ind2] == rotateArray[mid]:
                        # 顺序查找
                        result = rotateArray[ind1]
                        for i in range(ind1, ind2):
                            if rotateArray[i] < result:
                                result = rotateArray[i]
                        return result
                    elif rotateArray[mid] >= rotateArray[ind1]:
                        ind1 = mid
                    elif rotateArray[mid] <= rotateArray[ind2]:
                        ind2 = mid
            return rotateArray[mid]
发表于 2020-10-01 00:13:25 回复(0)
Python
大厂爸爸有offer吗头像 大厂爸爸有offer吗
python暴力解法 用排序函数
class Solution:
    def __init__(self):
        self.array1=[]
    def minNumberInRotateArray(self, rotateArray):
        self.array1=sorted(rotateArray)
        return(self.array1[0])
发表于 2020-08-28 18:06:04 回复(0)
Python
jianlinp头像 jianlinp
拿中点值与左端点进行比较，缩小查找范围
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
        left = 0
        right = len(rotateArray) - 1
        while left < right:
            mid = (left + right) / 2
            x = rotateArray[mid]
            if x == rotateArray[left]:
                left += 1
            elif x > rotateArray[left]:
                left = mid 
            else:
                if rotateArray[mid-1] > x:
                    return x
                right = mid - 1
        return rotateArray[right]
发表于 2020-08-13 15:29:11 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0
        num = rotateArray[0]
        for i in range(1,len(rotateArray)):
            if rotateArray[i] < num:
                num = rotateArray[i]
                break
        return num
1,注意非递减排序的数组的定义：递增序排列，但并非单调递增（可以重复），比如：1,2,3,4,4,6,7,9,9.
2，因为是旋转数组，所以循环在遇到第一个比array[0]小的数就会跳出循环。

发表于 2020-07-23 10:44:40 回复(0)
Python
学习了嘛嘛！！头像 学习了嘛嘛！！

需要考虑三种情况：
(1)array[mid] > array[high]:
出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
low = mid + 1
(2)array[mid] == array[high]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试 ，
high = high - 1
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
high = mid
注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid - 1，就会产生错误， 因此high = mid
但情形(1)中low = mid + 1就不会错误



# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
        left = 0
        right = len(rotateArray) - 1
        while left <= right:
            mid = (left + right) / 2
            if rotateArray[mid] > rotateArray[right]:# 中间元素位于前面的递增子数组
                left = mid + 1
            elif rotateArray[mid] < rotateArray[right]:# 中间元素位于后面的递增子数组
                right = mid# 如果是-1会错误
            else:
                right -= 1# 出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]
                #此时最小数字不好判断在mid左边右边，只好一个一个试

            if left >= right:
                break
        return rotateArray[left]# 如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字
发表于 2020-07-02 20:44:56 回复(0)
提交观点

问题信息

二分
难度：
140条回答 277381浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号