首页 > 试题广场 > 旋转数组的最小数字
[编程题]旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{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 回复(114)
# -*- 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)

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        min=rotateArray[0]
        if len(rotateArray)==0:
            return 0
        for i in range(len(rotateArray)):
            if rotateArray[i] < min:
               min=rotateArray[i]
        return min
                    

发表于 2019-05-12 14:37:24 回复(0)
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 = int((left + right)/2)
                if rotateArray[left] < rotateArray[mid]:
                    left = mid
                elif rotateArray[left] > rotateArray[mid]:
                    right = mid
                else:
                    return rotateArray[right]

编辑于 2019-05-07 16:14:00 回复(0)
第一种办法
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        len1=len(rotateArray)
        index1=0
        index2=len1-1
        while rotateArray[index1]>=rotateArray[index2]:
            if index2-index1==1:
                min=index2
                break
            mid=(index2+index1)/2
            if rotateArray[mid]>=rotateArray[index1]:
                index1=mid
            elif rotateArray[mid]<=rotateArray[index2]:
                index2=mid
        return rotateArray[min]

第二种办法
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        len1=len(rotateArray)
        min=rotateArray[0]
        for i in range(len1):
            if rotateArray[i]<min:
                min=rotateArray[i]
        return min

发表于 2019-04-25 22:45:32 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0   #空数组返回0
        #else:
            #return min(list(rotateArray))   #內建函数
        elif len(rotateArray) == 1:
            return rotateArray[0]   #1元素数组返回元素值
        else:
            #非减排序,也就是说增序呗    对比查找,第一个比前一位小的数
            for i in range(len(rotateArray)):
                if rotateArray[i]>rotateArray[i+1]:
                    return rotateArray[i+1]                

发表于 2019-04-24 12:01:51 回复(0)
python实现,暴力遍历(没想太多>.<)
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
    if len(rotateArray)==0:
        return 0
    if len(rotateArray)==1:
        return rotateArray[0]
    i,j=0,1
    while rotateArray[j]>=rotateArray[i]:
        i+=1
        j+=1
    return rotateArray[j]

另一种想法是二分:

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        len_=len(rotateArray)
        
        if len_==0:
            return 0
        if len_==1:
            return rotateArray[0]
        
        len_=len_-1
        
        r=len_
        l=0
        m=(r+l)/2
        
        while r-l>1:
            if rotateArray[m]>=rotateArray[l]:
                m,l=(r+m)/2,m
                continue
            else:
                m,r=(l+m)/2,m
                
        return rotateArray[r]


编辑于 2019-04-16 14:37:34 回复(0)
#min版(O(n))
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if rotateArray==[]:
            return 0
        else:
            return min(rotateArray)
#二分版(O(nlogn) class Solution:     def minNumberInRotateArray(self, rotateArray):         # write code here         if rotateArray==[]:             return 0         else:             min_num=rotateArray[0]             #考虑重复数字处分开情况             while rotateArray[-1]==min_num:                 rotateArray.pop()             l, r = 0, len(rotateArray) - 1             while l<=r:                 mid=(l+r)//2                 if rotateArray[mid]>=min_num:                     l=mid+1                 else:                     min_num=rotateArray[mid]                     r=mid-1         return min_num

编辑于 2019-04-14 00:30:52 回复(0)
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        index1 = 0
        index2 = len(rotateArray) - 1
        while index2-index1 > 1:
            indexMid = (index1+index2)//2
            if rotateArray[index2] >= rotateArray[indexMid]:
                index2 = indexMid
            elif rotateArray[index1] <= rotateArray[indexMid]:
                index1 = indexMid
        return rotateArray[index2]
为何这样通过了全部案例,我在自己的IDE上明显通不过几个特殊案例,如倒转0个元素。
编辑于 2019-04-12 18:24:04 回复(0)
 
# 是我理解错了题目的意思吗?怎么感觉不需要用到很复杂的算法啊?

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray) == 0:
            return 0
        return min(rotateArray)

发表于 2019-04-10 13:42:15 回复(0)
来一个正常的python
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        length=len(rotateArray)
        if length==0:
            return 0
        elif length==1:
            return rotateArray[0]
        elif len(list(set(rotateArray)))==1:
            return rotateArray[0]
        else :
            left=0
            right=length-1
            while rotateArray[left]>=rotateArray[right] and right-left>1:
                mid=(left+right)//2
                if rotateArray[mid]>rotateArray[right]:
                    left=mid
                else:
                    right=mid
            return rotateArray[right]
来一个清流
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray)==0:
            return 0
        else:
            return min(rotateArray)

你也不能说我作弊嘛,人生苦短
发表于 2019-04-06 18:22:53 回复(0)
def Find_min(list): if len(list) == 0: return 0  for i in range(len(list)): if list[i]-list[-i-1] < 0: if list[i] < list[-(i-1)-1]: return list[i] else: return list[-(i-1)-1]

#-------------------------------------------
ps:这应该是最短的代码了吧。
思路是这样的:
循环用列表的第i个元素减去倒数第i个元素,如果答案小于0了,那么有两种情况:
    1.如果旋转部分的长度大于未旋转部分,那么此时应该是旋转部分的头部作为[被减数]了,也就是说第i个元素就是我们要找的。
    2.如果旋转部分小长度小于为旋转部分,那么此时应该是未旋转部分的尾部作为[减数]了,所以这时倒数的第i-1个元素使我们要找的。

那么如何判断是哪一种情况呢,很简单,只要判断第i个元素和倒数第i-1个元素,那一个小,哪个就是我们要找的。

发表于 2019-04-06 16:26:45 回复(0)
# -*- coding:utf-8 -*-
#python 的二分查找,好像一直没人写
# -*- coding:utf-8 -*- class Solution:     def minNumberInRotateArray(self, rotateArray):         # write code here                  b=list(rotateArray)         lens=len(b)         low = 0          high = lens-1         while low < high:             mid = int(low + (high+1 - low) / 2)             if b[mid] > b[high]:                 low = mid              elif b[mid] == b[high]:                 #low=low+1                 high=high-1             else:                 high = mid         low=low+1         return b[low]         '''         if(rotateArray==[]):             return 0         i=0         while(i<len(rotateArray)-1):             if(rotateArray[i]<=rotateArray[i+1]):                 i+=1             else:                 return rotateArray[i+1]         if(i==len(rotateArray)-1):             return rotateArray[0]         '''
python 的二分查找,好像一直没人写

编辑于 2019-04-05 23:46:47 回复(1)
自己a了个Python的,请多指教
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
         i = len(rotateArray)
         if i==0:
             return 0 
         elif rotateArray[0]<rotateArray[i-1]:
             return rotateArray[0]
         else:
             idx = 0
             while idx<i:
                 if rotateArray[idx]>rotateArray[idx+1]:
                     return rotateArray[idx+1]
                 else:
                     idx+=1
发表于 2019-04-02 15:47:03 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray)<1:
            return None
        if len(rotateArray)==1:
            return rotateArray[0]
        left, right = 0, len(rotateArray)-1
        mid = left
        while rotateArray[left] >= rotateArray[right]:
            if left+1 == right:
                mid = right
                break
            mid = left + (right - left)//2
            # 如果left, mid, right三个指针对应的数组元素值相等,那么需要按顺序查找最小值,比如[1,0,1,1,1]和[1,1,1,0,1]
            if rotateArray[left] == rotateArray[mid] and rotateArray[mid] == rotateArray[right]:
                for i in range(left, right):
                    if rotateArray[i] < rotateArray[left]:
                        result = rotateArray[i]
                return result

            if rotateArray[mid] >= rotateArray[left]:
                left = mid
            elif rotateArray[mid] <= rotateArray[right]:
                right = mid
        return rotateArray[mid]


发表于 2019-03-28 20:59:48 回复(0)
二分法策略
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        flag_1 = 0
        flag_3 = len(rotateArray)-1
        flag_2 = int((flag_3+flag_1)/2)
        if len(rotateArray) == 0:
            return 0
        else:
            while 1:
                if rotateArray[flag_2] >= rotateArray[flag_1]:
                    flag_1 = flag_2
                    flag_2 = int((flag_3+flag_1)/2)
                else:
                    flag_3 = flag_2
                    flag_2 = int((flag_3+flag_1)/2)
                if (flag_2-flag_1) < 1:
                    break
            return rotateArray[flag_3]

发表于 2019-03-27 21:37:29 回复(0)