首页 > 试题广场 >

旋转数组的最小数字

[编程题]旋转数组的最小数字
  • 热度指数：1444775 时间限制：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)
Javascript
牛客284536955号头像 牛客284536955号
function minNumberInRotateArray( nums ) {
    // write code here
    for(let i=0;i<nums.length;i++){
        if(nums[i]>nums[i+1]){
            return nums[i+1]
        }
    }
    return nums[0]
}
发表于 2024-08-29 19:06:57 回复(0)
Javascript
Lyonnnnnn头像 Lyonnnnnn
function minNumberInRotateArray(rotateArray)
{
    // write code here
    return Math.min.apply(null,rotateArray);
}
发表于 2022-07-04 17:12:32 回复(0)
Javascript
纯海之蓝头像 纯海之蓝
function minNumberInRotateArray(rotateArray)
{
    // write code here
  if(rotateArray.length === 1) return rotateArray[0]
    let l = 0;
    let r = rotateArray.length -1
    let min = rotateArray[0]
    for(let i=0; i< rotateArray.length;i++) {
      let mid = l + Math.floor((r-l)/2)
      //处于临界，正好中位数是阶梯的临界点，则中位数右侧则是最小数
      if(rotateArray[mid] > rotateArray[mid + 1]) {
        min = rotateArray[mid + 1]
      } else if(rotateArray[mid] > rotateArray[0]){
        //中位数大于起始值，说明最小值在右侧
        l = mid
      } else {
        r = mid
      }
    }
    return min
}
发表于 2022-04-28 16:15:35 回复(0)
Javascript
summer_swilder头像 summer_swilder
js 一行搞定
function minNumberInRotateArray(rotateArray)
{
    return rotateArray.sort((a, b) => a-b)[0];
}
module.exports = {
    minNumberInRotateArray : minNumberInRotateArray
};
发表于 2022-04-23 13:11:50 回复(0)
Javascript
nicole27头像 nicole27 
function minNumberInRotateArray(rotateArray)
{
    // write code here
    let first = 0;
    let last = rotateArray.length-1;
    while(first<=last){
        if(rotateArray[first]<rotateArray[last]){
            return rotateArray[first];
        }else {
            for(let i = last;i>0;i--){
                if(rotateArray[i]>=rotateArray[i-1]){
                    continue;
                }else{
                    return rotateArray[i];
                }
        }
    }
}
}

发表于 2022-03-16 17:41:34 回复(0)
Javascript
AAATest头像 AAATest 
function minNumberInRotateArray(rotateArray) {
    // write code here

    //  旋转后是这样子的 - _ - 两边大, 中间小, 一直逼近最中间
    //  直到两个标记位遇见即可
    if (!rotateArray.length) return -1

    let pre = 0, last = rotateArray.length - 1

    while (pre < last) {
        rotateArray[pre] >= rotateArray[last] && pre++
        rotateArray[pre] <= rotateArray[last] && last--
    }
    return rotateArray[pre]
}
发表于 2022-03-11 11:55:19 回复(0)
Javascript
天网-__-头像 天网-__-

虽然是简单题，但有两个坑。

一个是如果 如果mid中间值大于右边界的值的话，mid一定不在左边，且mid一定不可能是最小值，所以 l=mid+1，如果mid中间值小于右边的元素的话，mid可能就是最小值，所以更新r=mid。

二是mid值必须和右边界进行比较，因为和左边界比较时，如果当前区间是有序的，则无法正确的确定最小值在那个区间，比如[8, 1, 2, 3]，第二次比较时，mid值等于2，比左边界1大，但是最小值应该在左边。

function minNumberInRotateArray(rotateArray)
{
    let l=0,r=rotateArray.length-1;
    while(l < r) {
        const mid = l + Math.floor((r-l)/2);
        if (rotateArray[mid] > rotateArray[r]) {
            l = mid+1;
        } else if (rotateArray[mid] < rotateArray[r]){
            r = mid;
        } else {
            --r;
        }
    }
    return rotateArray[l];
}
发表于 2021-12-30 13:08:38 回复(0)
Javascript
Active_Waylon头像 Active_Waylon 
// 你可以使用O(logN)的时间复杂度通过该题吗?
function minNumberInRotateArray(rotateArray)
{
    // write code here
    // 解法1 暴力法
    // return Math.min(...rotateArray);
    
    // 解法2 二分法
    
    let n = rotateArray.length-1;
    if(n<0) {
        return 0;
    }
    //  二分查找，
    // 要达到二分性质，需要使前半段 nums[i] >= nums[0] 后半段 nums[i]<nums[0]
    // 去除第二段末尾与nums[0]相等的元素
    while(rotateArray[n] == rotateArray[0] && n > 0) {
        n--;
    }
    if(rotateArray[n] >= rotateArray[0]) {
        return rotateArray[0];
    }
    // 开始二分
    let left = 0;
    let right = n;
    while(left < right) {
        let mid = left+right >> 1;
        if(rotateArray[mid] < rotateArray[0]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return rotateArray[right];
}

发表于 2021-09-14 23:17:14 回复(0)
JavaScript
NPC201904301802722头像 NPC201904301802722 
function minNumberInRotateArray(rotateArray)
{
    if(rotateArray.length==0){
      return 0
    }
    let left=0
    let right=rotateArray.length-1

    while(rotateArray[left]>=rotateArray[right] && left<right){
      let mid=(left+right)>>1
      if(rotateArray[mid]>=rotateArray[left]){
        left=mid+1
      }else{
        right=mid
      }
    }
    return rotateArray[left]
}
javascript击败99%。思路是最终left到right里面是从小到大排序的数组。取left的值就行了。
编辑于 2021-06-15 18:23:34 回复(2)
JavaScript
只小只头像 只小只
JavaScript 
function minNumberInRotateArray(rotateArray)
{
    if(!rotateArray)
        return 0;
    for(let i=rotateArray.length-1;i>0;i--){
        if(rotateArray[i-1]>rotateArray[i])
            return rotateArray[i];
    }
}


编辑于 2021-06-08 21:14:41 回复(0)
JavaScript
简20180711000791头像 简20180711000791
function minNumberInRotateArray(rotateArray)
{
    // write code here
    if(rotateArray.length === 0) {
        return 0;
    }
    return Math.min.apply(null , rotateArray)
}
发表于 2021-05-24 19:00:18 回复(0)
JavaScript
Mithrandir_74头像 Mithrandir_74
应该是最简单的方法
直接暴力求解最小值 
function minNumberInRotateArray(rotateArray)
{
    // write code here
     if(rotateArray.length == 0)
        return 0;
    return Math.min(...rotateArray);
}
发表于 2021-03-15 17:43:51 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function minNumberInRotateArray(rotateArray)
{
    var length = rotateArray.length;
    var first = 0;
    var target = length - 1;
    var mid = Math.floor((length-1)/2);
    while(first!=target){
        if(rotateArray[mid]<rotateArray[target]){
            target = mid;
            mid = Math.floor((first + target)/2);
        }else if(rotateArray[mid]>rotateArray[target]){
            first = mid + 1;
            mid = Math.floor((first + target)/2);
        }else{
            target = target - 1 ;
            mid = Math.floor((first + target)/2);
        }
    }
    return rotateArray[first];
}

发表于 2021-03-05 13:00:33 回复(0)
JavaScript
别卷啦！头像 别卷啦！
二分法 
function minNumberInRotateArray(rotateArray)
{
    // write code here
    let left = 0,right=rotateArray.length-1,mid,a=rotateArray
    if(a[left]<a[right]||a.length== 0){
        return a[left];
    }
    while(left<right){
        mid = (right+left)>>1
        if(a[mid]>a[right]){
            left = mid + 1
        } else if(a[mid]<a[right]){
           right = mid
        } else {
            right--
        }
    }
    return a[left]
}


发表于 2020-12-18 11:36:16 回复(0)
JavaScript
SilverCoin头像 SilverCoin 
function minNumberInRotateArray(rotateArray)
{
    let len = rotateArray.length
    let left = 0
    let right = len - 1
    let mid
    
    // 边界判断
    if (len == 0) {
        return 0
    }
    
    // 考虑没有旋转的情况
    if (rotateArray[right] > rotateArray[left]) {
        return rotateArray[0]
    }
    
    
    while (left <= right) {
        mid = left + ((right - left) >> 1)
        
        // 如果 mid > mid + 1, 那说明 mid + 1位置就是旋转点
        if (rotateArray[mid] > rotateArray[mid + 1]) {
            return rotateArray[mid + 1]
        }
        
        // 如果 mid < mid - 1, 那说明 mid 位置就是旋转点
        if (rotateArray[mid] < rotateArray[mid - 1]) {
            return rotateArray[mid]
        }
        
        // 因为旋转的一个判定就是第一个元素肯定大于最后一个元素, 所以通过第一个元素就可以移动mid
        if (rotateArray[mid] > rotateArray[0]) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
}

发表于 2020-11-30 22:01:52 回复(0)
JavaScript
许愿2020offer头像 许愿2020offer 
function minNumberInRotateArray(rotateArray)
{
    return Math.min(...rotateArray)
    //此处使用的是ES6扩展运算符
    // write code here
}
二分法还未写出来

发表于 2020-08-17 17:06:20 回复(0)
JavaScript
ULG头像 ULG
 采用二分法解答这个问题，（这里和递增数组有区别）
mid =right + (right - left)/2
需要考虑三种情况：
(1)array[mid] > array[right ]:
出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
left= mid + 1
(2)array[mid] == array[right ]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试 ，
right = right - 1
(3)array[mid] < array[right ]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
right = mid
注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字
比如 array = [4,6]
array[left] = 4 ;array[mid] = 4 ; array[right] = 6 ;
如果right = mid - 1，就会产生错误， 因此right = mid
但情形(1)中left 
function minNumberInRotateArray(rotateArray)
{
    // write code here
    let len = rotateArray.length
    if(!len){
        return 0
    }
    let left = 0
    let right = len - 1
    while(left < right){
        let mid = Math.floor(left + (right -left)/2)
        if(rotateArray[mid] > rotateArray[right]){
            left = mid + 1
        }else if(rotateArray[mid] === rotateArray[right]){
            right = right - 1
        }else{
            right = mid
        }
    }
    return rotateArray[left]
}

= mid + 1就不会错误
发表于 2020-07-18 14:59:28 回复(0)
JavaScript
Lrenz头像 Lrenz
if(!rotateArray.length){
        return 0;
    }else{
        var min = 0;
        for (var i = 0; i < rotateArray.length; i++) {
            min = rotateArray[0];
            if (min <= rotateArray[1]) {
                rotateArray.push(rotateArray.shift());

            } else {
                rotateArray.push(rotateArray.shift());
                return rotateArray[0];
            }
        }
        return rotateArray[0];
    }
发表于 2020-03-26 16:02:54 回复(0)
JavaScript
努力长胖的强强头像 努力长胖的强强
二分法，使用判断，确定位于后半部分，并且存在arr=[1, 1, 1, 0, 1, 1]情况时，时间复杂度也为O（logn）

function minNumberInRotateArray(rotateArray)
{
// write code here
if (rotateArray.length == 0) {
return 0;
}
let left = 0;
let right = rotateArray.length - 1;
while(left < right) {
let mid = parseInt((left + right) / 2);
// 下面的判断语句是核心所在
if(rotateArray[mid] >= rotateArray[left] && rotateArray[mid] >= rotateArray[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return rotateArray[right]
}
编辑于 2020-02-27 16:46:40 回复(0)
提交观点

问题信息

二分
难度：
69条回答 286339浏览

热门推荐

通过挑战的用户

查看代码

相关试题

旋转数组的最小数字

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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