首页 > 试题广场 > 旋转数组的最小数字
[编程题]旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
推荐
思路

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


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

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

思路:

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

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

(2)找到数组的中间元素。

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

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

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

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

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

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

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

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

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

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

我们看一组例子:{1,0,11,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 回复(130)
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        res = sorted(rotateArray)
        return res[0]
发表于 2019-10-18 22:00:54 回复(0)
原本想用递归做的,但给定的形参里少了两个变量(left和right),不想再建函数了,就直接用双指针完成,要注意分析题目要求,考虑符合的条件,即mid小于或大于其两边的数字,这样后面继续二分就好做了
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        l=0
        r=len(rotateArray)-1
        while l<=r:
            if l==r:
                return rotateArray[l]
            mid=l+(r-l)//2
            if rotateArray[mid]<rotateArray[mid-1]:
                return rotateArray[mid]
            if rotateArray[mid]>rotateArray[mid+1]:
                return rotateArray[mid+1]
            if rotateArray[mid]<rotateArray[l]:
                r=mid-1
            else:
                l=mid+1


发表于 2019-10-15 20:11:37 回复(0)
这个题的思路就是让第一跟剩下所有比较,如果此时是完全升序,则第一个元素就是最小的。如果是乱序的话,其遇见的第一个比其小的元素就是最小元素

发表于 2019-10-12 20:29:47 回复(0)
classSolution:
   defminNumberInRotateArray(self, rotateArray):
       # write code here
       ifnotrotateArray:
           return0
       else:
           returnmin(rotateArray)
发表于 2019-10-05 13:06:32 回复(0)
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
            else:
                right = mid
        return rotateArray[left]


发表于 2019-10-05 02:34:39 回复(0)
## 二分查找
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray)==0:
            return 0
        elif len(rotateArray)==1:
            return rotateArray[0]
        else:
            left,right=0,len(rotateArray)-1
            while left<right:
                mid=(left+right)//2
                if rotateArray[mid]>rotateArray[right]:
                    left=mid+1
                else:
                    right=mid
            return rotateArray[left]

## 比较
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray)==0:
            return 0
        elif len(rotateArray)==1:
            return rotateArray[0]
        else:
            for i in range(len(rotateArray)-1):
                if rotateArray[i]>rotateArray[i+1]:
                    return rotateArray[i+1]
            return rotateArray[0]
## 重新排列
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        while rotateArray[-1]<=rotateArray[0]:
            rotateArray.insert(0,rotateArray.pop(-1))
        return rotateArray[0]


编辑于 2019-10-21 18:38:47 回复(0)
题目中的乱七八糟的描述都是干扰的,
什么旋转不旋转,老夫拿起min()函数就是干!
直接求最小的那个元素即可。
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray) == 0:
            return 0
        else:
            return min(rotateArray)


发表于 2019-10-01 18:17:08 回复(0)
#非递减表示不变或者递增
#查找array[i]<array[i-1]即可
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        for i in range(1,len(rotateArray)):
            if rotateArray[i]<rotateArray[i-1]:
                return rotateArray[i]
            

发表于 2019-09-02 21:20:42 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray) == 0:
            return 0
        else:
            lo = 0
            hi = len(rotateArray) - 1
            while lo < hi:
                if rotateArray[lo] < rotateArray[hi]:
                    return rotateArray[lo]
                mid = lo + (hi-lo) // 2
                if rotateArray[lo] < rotateArray[mid]:
                    lo = mid + 1
                elif rotateArray[mid] < rotateArray[hi]:
                    hi = mid
                else:
                    lo += 1
            return rotateArray[lo]

编辑于 2019-08-15 17:33:11 回复(0)
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0
        if len(rotateArray) == 1:
            return rotateArray[0]
        left, right = 0, len(rotateArray) - 1
        while left <= right:
            mid = (left + right) >> 1
            if rotateArray[mid] > rotateArray[right]:
                left = mid + 1
            elif rotateArray[mid] < rotateArray[right]:
                right = mid
            else:
                right -= 1
            if left >= right:
                break
        return rotateArray[left]

编辑于 2019-08-10 21:14:39 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        n=len(rotateArray)-1
        for j in range(0,n):
                if rotateArray[j]<rotateArray[0]:
                    return rotateArray[j]

遍历找到比第一个数小的则是最小的。

发表于 2019-08-06 15:37:37 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        length = len(rotateArray)
        if length == 0:
            return 0
        elif length == 1:
            return rotateArray[0]
        else:
            start = 0
            end = length - 1
            mid = int((start + end)/2)
            if rotateArray[mid] > rotateArray[end]:
                return self.minNumberInRotateArray(rotateArray[mid+1:end+1])
            else:
                return self.minNumberInRotateArray(rotateArray[start:mid+1])
发表于 2019-07-25 23:33:29 回复(0)
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray)==0:
            return 0
        else:
            return min(rotateArray)

这样是不是要死啊??
啥子情况,通过了
发表于 2019-07-21 02:25:52 回复(0)
#旋转数组的最小数字//参照剑指offer,哈哈哈搬运工而已,方便自己学习
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:#判断是否为空数组
            return None
        index1 = 0 #定义两个下指标
        index2 = len(rotateArray) - 1
        indexMid = index1
         
        while rotateArray[index1] >= rotateArray[index2]:
            #两个下指标指向相邻数字,则index2是数组中的最小数字
            if index2 - index1 == 1:
                indexMid = index2
                break
            #这里注意加int()    
            indexMid = int((index1 + index2)/2)
            #如果下标为index1、index2和indexMid指向的三个数字相等,则只能按顺序查找
            if rotateArray[index1] == rotateArray[index2] and rotateArray[index1] == rotateArray[indexMid]:
                return MinInOrder(rotateArray,index1,index2)
             
            if rotateArray[indexMid] >= rotateArray[index1]:
                index1 = indexMid
             
            elif rotateArray[indexMid] <= rotateArray[index2]:
                index2 = indexMid
                 
        return rotateArray[indexMid]
     
    def MinInOrder(rotateArray,index1,index2):
        result = rotateArray[index1]
        for i in range(index1+1,index2+1):
            if result > rotateArray[i]:
                result = rotateArray[i]
                 
        return result
        

发表于 2019-07-20 13:06:38 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        n = len(rotateArray)
        if n == 0:
            return 0
        else:
            return min(rotateArray)
不知道这样行不行。。。
发表于 2019-07-13 16:24:44 回复(0)
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0
        l = 0
        h = len(rotateArray)-1
        while l < h:
            m = l + (h-l)/2
            if (rotateArray[l] == rotateArray[m] and rotateArray[m] == rotateArray[h]):
                return min(rotateArray[l],rotateArray[h])
            elif rotateArray[m] <= rotateArray[h]:
                h = m
            else:
                l = m + 1
        return rotateArray[l]
思路:二分查找的变形
来自cyc大佬的思路:将旋转数组对半分可以得到一个包含最小元素的新旋转数组,以及一个非递减排序的数组。新的旋转数组的数组元素是原数组的一半,从而将问题规模减少了一半,这种折半性质的算法的时间复杂度为 O(logN)

此时问题的关键在于确定对半分得到的两个数组哪一个是旋转数组,哪一个是非递减数组。我们很容易知道非递减数组的第一个元素一定小于等于最后一个元素。

通过修改二分查找算法进行求解(l 代表 low,m 代表 mid,h 代表 high):

  • 当 nums[m] <= nums[h] 时,表示 [m, h] 区间内的数组是非递减数组,[l, m] 区间内的数组是旋转数组,此时令 h = m;
  • 否则 [m + 1, h] 区间内的数组是旋转数组,令 l = m + 1。

发表于 2019-07-09 22:17:33 回复(0)
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray)==0:
            return 0
        if rotateArray[0] < rotateArray[-1]:
            return rotateArray[0]
        low = 0
        high = len(rotateArray) - 1
        mid = int((low + high) / 2)
        minimum = rotateArray[0]
        if rotateArray[low]==rotateArray[mid] and rotateArray[mid]==rotateArray[high]:
            for i in rotateArray:
                if i<minimum:
                    minimum = i
            return minimum
        while(low<high-1):
            mid = int((low + high) / 2)
            if rotateArray[mid]>rotateArray[high]:
                low = mid
            elif rotateArray[mid]<rotateArray[high]:
                high = mid
        return rotateArray[high]

我自己写的Python代码在牛客网里死活通不过,但是在本地我运行了很多例子都对了。反倒是我在回答里复制了几个答案,在牛客网通过了,但是我在本地输入了几个例子,他们通不过。
上面是我写的代码
发表于 2019-07-08 22:21:01 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        first = 0
        last = len(rotateArray)-1
        while last - first !=1:
            if rotateArray[first]<rotateArray[last]:
                return rotateArray[0]
            mid = (first+last)/2
            if rotateArray[first]==rotateArray[last] and rotateArray[first]==rotateArray[mid]:
                return self.selectmin(rotateArray)
            if rotateArray[mid]>=rotateArray[first]:
                first = mid
            if rotateArray[mid]<=rotateArray[last]:
                last = mid
        return  rotateArray[last]
    def selectmin(self,rotateArray):
        _min = rotateArray[0]
        for i in range(1,len(rotateArray)):
            if rotateArray[i]<_min:
                _min = rotateArray[i]
        return _min


发表于 2019-06-13 19:12:18 回复(0)
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        left = 0
        right = len(rotateArray) - 1
        while right - left > 1:

            mid = left + (right - left) // 2
            if rotateArray[mid] == rotateArray[left] and rotateArray[mid] == rotateArray[right]:
                return min(rotateArray)
            if rotateArray[mid] >= rotateArray[left]:
                left = mid
                # 注意要continue
                continue
            if rotateArray[mid] <= rotateArray[left]:
                right = mid
        return rotateArray[right]
发表于 2019-05-30 10:33:01 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if rotateArray:
            i = 0
            minE = rotateArray[0]   #假如全部一样,就取第一个咯
            ksize=len(rotateArray)
            while (i<ksize-1):
                if rotateArray[i] <= rotateArray[i+1]:
                    i = i + 1
                else:   #一直向右移动,直到找到突然下降的数,跳出循环。
                    #if rotateArray[i] <= min(rotateArray[i - 1], rotateArray[i + 1]):
                    minE = rotateArray[i+1]
                    break
            return minE
        else:
            return 0
                

#思路就是找出下降点,就跳出循环
发表于 2019-05-28 16:44:14 回复(0)