首页 > 试题广场 >

旋转数组的最小数字

[编程题]旋转数组的最小数字

热度指数：1413083 时间限制：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 \le n \le 10000$ ，数组中任意元素的值: $0 \le val \le 10000$

要求：空间复杂度： $O(1)$ ，时间复杂度： $O(logn)$

示例1

输入

[3,4,5,1,2]

输出

示例2

输入

[3,100,200,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 3

Huanhuan160

class Solution:

def minNumberInRotateArray(self , nums: List[int]) -> int:

# write code here

return min(nums)

#直接找到最小值就全部通过了

编辑于 2024-04-02 20:18:59 回复(0)

Python 3

牛客535858453号

start = 0

end = len(nums)-1

while start < end:

mid = (start+end)//2

if nums[mid] > nums[start]:

if nums[start] < nums[end]:

end = mid

else:

start = mid + 1

elif nums[mid] < nums[end]:

end = mid

else:

start +=1

return nums[start]

发表于 2023-12-10 15:06:21 回复(0)

Python 3

11111111b

这题目有重复，不能用二分法做吧。咋还有一个[1,0,1,1,1]的测试用例

发表于 2023-10-23 22:15:22 回复(0)

Python 3

蓝鲸与风

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param rotateArray int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # write code here
        rotateArray.sort()
        return rotateArray[0]

发表于 2022-08-18 22:25:15 回复(1)

Python 3

风软一江山

#挨个找后一位比前一位小的数
class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        left = 0
        try:
            while rotateArray[left] <= rotateArray[left+1]:
                    left += 1
            return rotateArray[left+1]
        except IndexError:
            return rotateArray[0]

发表于 2022-07-27 00:56:16 回复(2)

Python 3

牛客555680711号

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # write code here
        marker = rotateArray[-1]
        n = len(rotateArray)
        if n==1: return marker
        i, j = 0,n-1
        while i < j:
            if rotateArray[i] < rotateArray[j]: #提前结束：[1,0,1,1,1]
                return rotateArray[i]
            mid = (i+j)//2
            if rotateArray[mid] > marker:
                i = mid+1
            elif rotateArray[mid] < marker:
                j = mid
            else: i+= 1 #收缩范围一步
        return rotateArray[i]

发表于 2022-07-11 16:22:28 回复(0)

Python 3

来牛客玩玩

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # write code here
        for i in range(len(rotateArray)-1):
            if rotateArray[i] > rotateArray[i+1]:
                return rotateArray[i+1]
        return rotateArray[0]

发表于 2022-07-09 07:30:26 回复(0)

Python 3

RigaYang

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        m = len(rotateArray)
        ref = rotateArray[0]
        for i in range(1,m):
            if rotateArray[i] < ref:
                return rotateArray[i]
        return ref
        # write code here

发表于 2022-07-03 16:14:06 回复(0)

Python 3

Vivimore

二分法
时间复杂度：O(logn) 空间复杂度：O(1)

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        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 -= 1
            else:
                right = mid
        return rotateArray[left]

发表于 2022-05-16 15:34:12 回复(0)

Python 3

牛客828904495号

这样通过作数吗？

发表于 2022-04-25 14:02:57 回复(0)

Python 3

牛客496433704号

class Solution:
def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
if len(rotateArray)==0:
return 0
elif len(rotateArray)==1:
return rotateArray[0]
else:
if rotateArray[-1]>rotateArray[0]:
return rotateArray[0]
else:
i=1
while (rotateArray[i]>=rotateArray[i-1]) and (i<len(rotateArray)):
i=i+1
if i==len(rotateArray)-1:
return rotateArray[-1]
else:
return rotateArray[i]

发表于 2022-04-16 14:27:54 回复(0)

Python 3

小小小小燃

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        
        # write code here
        left, right = 0, len(rotateArray)-1
        
        while left < right:
            mid = int(0.5 * (left + right))
            
            if rotateArray[mid] > rotateArray[right]:
                left = mid + 1
            elif rotateArray[mid] == rotateArray[right]:
                right = right - 1
            else:
                right = mid
            
        return rotateArray[right]

发表于 2022-04-10 11:02:10 回复(0)

Python 3

azedplayer

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # write code here
        if not rotateArray:
            return 0
        l,r = 0,len(rotateArray)-1
        while l<r:
            m = (l+r)>>1;
            if rotateArray[m] > rotateArray[r]:
                l = m+1
            elif rotateArray[m] < rotateArray[r]:
                r = m
            else:
                r = r-1
        return rotateArray[l]

发表于 2022-04-09 20:07:58 回复(0)

Python 3

刚好中意

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        start = 0
        end = len(rotateArray)-1
        while start<=end:
            mind = (start+end)//2
            if rotateArray[mind] > rotateArray[end]:
                start = mind+1
            elif rotateArray[mind] < rotateArray[end]:
                end = mind
            elif rotateArray[mind] == rotateArray[end]:
                end -= 1
        return rotateArray[mind]

发表于 2022-04-03 16:11:24 回复(0)