首页 > 试题广场 >

旋转数组的最小数字

[编程题]旋转数组的最小数字
  • 热度指数：1413219 时间限制：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)
C
一个优雅的程序猿头像 一个优雅的程序猿 
int minNumberInRotateArray(int* nums, int numsLen ) {
    int start=0, end=numsLen-1, mid;
  
    while(end-start>1) {
        mid = (end+start+1)/2;

        if( (nums[mid] < nums[end]))
            end = mid;
        else if( (nums[mid] > nums[end]))
            start = mid;
        else {
            if(nums[start]>=nums[end])
                start++;
            else
                end--;
        } 
    }
    return nums[start]>nums[end]?nums[end]:nums[start];
}

编辑于 2024-03-16 12:15:56 回复(0)
C
可以找到心仪工作头像 可以找到心仪工作
二分法但加了很多判断条件 
int minNumberInRotateArray(int* nums, int numsLen ) {
    if (numsLen == 1)
        return nums[0];

    int left = 0;
    int right = numsLen - 1;
    int mid = 0;
    while (left <= right)
    {
        mid = (right+left)/2;

        //如果只剩两个相邻元素进行比较,无法通过下标得知大小,因此直接判断两者的大小
        if (/*right == mid||*/ left == mid){
            if (nums[left]<nums[right]){
                mid = left;
            }
            else {
                mid = right;
            }
            break;
        }

        if (nums[right] == nums[mid] && nums[mid] == nums[left]){
            right = right - 1;//移动左侧和右侧都可以
        }
        else if (nums[mid]<nums[left] && nums[mid]<nums[right]){
            right = right - 1;//移动左侧和右侧都可以
        }
        else if (nums[right] >= nums[mid]){
            right = mid -1;
        }
        else if (nums[mid] >= nums[left]){
            left = mid + 1;
        }
        else {
            mid = right;//以上判断均不成立,说明左>=中>=右,右一定最小
            break;
        }

    }
    return nums[mid];
}


编辑于 2024-03-08 00:59:16 回复(0)
C
pdsu_张建洋头像 pdsu_张建洋
int minNumberInRotateArray(int* nums, int numsLen ) {
    // write code here
    int left = 0;
    int right = numsLen-1;
    while(right>left){
        int mid = (left+right)/2;
        if(nums[mid]>nums[right])
        {
            left=mid+1;
        }
        else if(nums[mid]<nums[right])
        {
             right=mid;
        }
        else{
            right--;
        }
    }
    return nums[right];
}
编辑于 2024-01-18 16:36:50 回复(0)
C
七分七分头像 七分七分
不就是求最小值吗？
int minNumberInRotateArray(int* nums, int numsLen )
{
    int k = nums[0];
    for(int i = 1;i < numsLen;i++)
    {
        k = nums[i-1] > nums[i] ? nums[i] : k;
    }
    return k;
}
发表于 2024-01-12 23:34:56 回复(1)
C
猪猪侠的飞天梦头像 猪猪侠的飞天梦 
/**  简单暴力解法
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @param numsLen int nums数组长度
 * @return int整型
 */
int minNumberInRotateArray(int* nums, int numsLen ) {
    // write code here
    int i = 0,j = 0;
    for(i = 0; i<numsLen-1; i++)
    {
        if(nums[i]>nums[i+1]) return nums[i+1];
    }
    return nums[0];

}


发表于 2023-11-30 14:19:33 回复(0)
C
陈让然头像 陈让然
感觉不用旋转数组的思维，直接变成找数组最小值了哈哈
主要是要区分好，已旋转部分和未旋转部分，两者都为非降序，关键点在于两部分的交互点，在这部分下手 
int minNumberInRotateArray(int* nums, int numsLen ) {
    // write code here
    int beg=0;
    int end=numsLen-1;
    int mid;
    while (beg<=end) 
    {
        mid=(beg+end)/2;
        //[4,5,1,2,3]
        if(nums[mid]<nums[beg])//说明nums[mid]<=[nums[mid+1],nums[end]],已旋转部分升序
        {
            end=mid;//min在[beg,mid]中
        }
        //[3,4,5,1,2]
        else if(nums[mid]>nums[end])//说明nums[mid]>=[nums[beg],nums[mid]],已旋转部分升序
        {
            beg=mid+1;//min在[mid+1,end]中
        }
        //[3,3,3,3,3]
        else//nums[mid]==nums[beg]||nums[mid]==nums[end]，举个例子而已
        {
            end--;//min在[beg,end-1]中
        }
    }
    return nums[beg];
}
eg.求数组元素最小值
 
int minNumberInRotateArray(int* nums, int numsLen ) {
    // write code here
     if(!nums||!numsLen)
     {
         return -1;
     }
    int min=nums[0];
    int index=0;
    while(index<numsLen)
    {
        if(min>=nums[index])
        {
            min=nums[index];
        }
        index++; 
    }
    return min;
}

发表于 2023-09-10 17:57:51 回复(0)
C
ChrisBosh头像 ChrisBosh 
int minNumberInRotateArray(int* nums, int numsLen ) 
{
    int min=nums[0];
   for (int i=0;i<numsLen-1;i++)
   {
    if ((nums[i]<=nums[i+1])&&(nums[i]<min))
        min=nums[i];
    
   }
   if (min<nums[numsLen-1])
    return min;
    else
     return nums[numsLen-1];
}

发表于 2023-08-09 18:47:50 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
int minNumberInRotateArray(int* nums, int numsLen )
{
    // write code here
    int left=0;
    int right=numsLen-1;
   
    while(left<=right)
    {
        int mid=left+(right-left+1)/2;
        if(nums[mid]<nums[mid-1])
        {
            return nums[mid];
        }
        else if(nums[mid]>nums[0])
        {
            left=mid+1;
        }
        else if(nums[mid]<nums[numsLen-1])
        {
            right=mid-1;
        }
        else
        {
            int i=left;
            while(i<=right)
            {
                if(nums[i]!=nums[mid])
                {
                    break;
                }
                ++i;
            }
            if(i<=mid)
            {
                right=mid;
            }
            else
            {
                left=mid;
            }
        }
    }
    return nums[0];
}
发表于 2023-07-11 16:49:29 回复(0)
C
zzx9头像 zzx9
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
int left=0;
int right=rotateArrayLen-1;
while(left<right)
{
    int mid=(left+right)/2;
    if(rotateArray[mid]<rotateArray[right])
    {
        right=mid;
    }
    else if(rotateArray[mid]>rotateArray[right])
    {
        left=mid+1;
    }
    else {
        right--;
    }
}
return rotateArray[left];
}
发表于 2023-04-03 13:12:15 回复(0)
C
焦虑的刷题者头像 焦虑的刷题者 
// 利用旋转数组的特点：最小值一定在最大值后面，最坏的情况在最前面
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    int* p = &rotateArray[rotateArrayLen-1];
    int count = 0;
    // 从后向前遍历，如果一直变小就继续往前，直到第一个大的数字，返回小数
    while((count < rotateArrayLen) && (*p >= *(p-1)))
    {
        p--;
        count++;
    }
    // 数组最小值在第一个位置
    if(count == rotateArrayLen)
        p = &rotateArray[0];

    printf("%d ",*p);
    return *p;
}


发表于 2023-01-20 11:13:26 回复(0)
C
神码_头像 神码_ 
/**
 * 
 * @param rotateArray int整型一维数组 
 * @param rotateArrayLen int rotateArray数组长度
 * @return int整型
 */
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) 
{
    // write code here
    int left=0;
    int right=rotateArrayLen-1;
   if(rotateArrayLen>2)
   { 
    while(left+1<right)
    {
        if(*(rotateArray+left)<*(rotateArray+right))
        {
            right--;
        }
        if(*(rotateArray+left)>*(rotateArray+right))
        {
            left++;
        }
        if(*(rotateArray+left)==*(rotateArray+right))
        {
            left++;
        }
    }
   }
   if(rotateArrayLen<2)
   {
    return *(rotateArray+left)>*(rotateArray+right)?*(rotateArray+right):*(rotateArray+left);
   }
    if(*(rotateArray+left)==*(rotateArray+right))
    {
        return *(rotateArray+left);
    }
    else
    {
        return *(rotateArray+left)>*(rotateArray+right)?*(rotateArray+right):*(rotateArray+left);

    }

}

发表于 2022-12-31 16:19:15 回复(0)
C
80后大叔头像 80后大叔 
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    // write code here
    int left=0, right=rotateArrayLen-1;
    while(left<right) {
        int mid = left+(right-left)/2;
        if(rotateArray[mid]>rotateArray[right]) left=mid+1;
        else if(rotateArray[mid]<rotateArray[right]) right=mid;
        else right--;
    }
    return rotateArray[right];
}
发表于 2022-11-14 17:36:24 回复(0)
C
yuyuyuya头像 yuyuyuya 
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen)
{
    // write code here
    int count = 0;
    int num = 0;
    for (int i = 0; i < rotateArrayLen; i++)
    {
        for (int j = 0; j < rotateArrayLen; j++)
        {
            if (rotateArray[i] <= rotateArray[j])
            {
                count++;
                if(count == rotateArrayLen)
                {
                    num = rotateArray[i];
                }
            }
          
        }
        count = 0;
    }
    return num;

}

发表于 2022-10-24 19:44:52 回复(0)
C
一个达布刘头像 一个达布刘 
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    // write code here
    for(int i=0;i<rotateArrayLen;i++)
    {
        if(rotateArray[i-1]>rotateArray[i])
            return rotateArray[i];
    }
    return rotateArray[0];
}

发表于 2022-09-11 21:27:22 回复(0)
C
熬夜花生头像 熬夜花生 
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    // write code here
    int i = 0;
    int left = 0;
    int right = rotateArrayLen - 1;
    while(left < right)
    {
        int mid = (left+right)/2;
        if((right - left) == 1)
        {
            return rotateArray[left]>rotateArray[right]?rotateArray[right]:rotateArray[left];
        }
        
        if(rotateArray[right] < rotateArray[mid])
        {
            left=mid;
        }
        else if(rotateArray[left] == rotateArray[mid] && rotateArray[right] == rotateArray[mid])
        {
            right--;
            left++;
        }
        else
        {
            right=mid;
        }
    }
    
    return rotateArray[left];
}

发表于 2022-07-25 12:10:11 回复(0)
C
忙碌的蚊不叮在思考头像 忙碌的蚊不叮在思考
题目说白了 不就是找一个数组里的最小值嘛 
static int min = 10000;
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    // write code here
    int i = 0;
    for(i = 0; i < rotateArrayLen;i++)
    {
        if(rotateArray[i]< min)
        {
            min = rotateArray[i];
        }
    }
    return min;
}
是不是有些取巧了😗😗

发表于 2022-07-13 15:29:08 回复(0)
C
呸看见你就开心头像 呸看见你就开心
//找第一个逆序的；如果都是非降序的，就是第一个数值
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    // write code here
        int i=0;
        while(rotateArray[i]<=rotateArray[i+1] && (i+2)<=rotateArrayLen){
            i++;
        }
        if(i==rotateArrayLen-1){
            return rotateArray[0];
        }else{
            return rotateArray[i+1];
        }
}
发表于 2022-03-12 17:02:14 回复(1)
C
学什么编程还不如去搬砖头像 学什么编程还不如去搬砖 
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    // write code here
    int min = *rotateArray;
    int i = 0;
    for(i=0;i<rotateArrayLen;i++)
    {
        int start = *rotateArray;
        if(start<min)
        {
           min = start; 
        }
        int j = 0;
        for(j=0;j<rotateArrayLen-1;j++)
        {
            *(rotateArray+j)=*(rotateArray+j+1);
        }
        *(rotateArray+rotateArrayLen-1)=start;
    }
    return min;
}
发表于 2022-01-30 15:54:15 回复(0)
提交观点

问题信息

二分
难度：
22条回答 279982浏览

热门推荐

通过挑战的用户

查看代码

相关试题

旋转数组的最小数字

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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