首页 > 试题广场 >

旋转数组的最小数字

[编程题]旋转数组的最小数字
  • 热度指数:1381163 时间限制: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,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 回复(141)
采用二分法解答这个问题,
mid = low + (high - low)/2
需要考虑三种情况:
(1)array[mid] > array[high]:
出现这种情况的array类似[3,4,5,6,0,1,2],此时最小数字一定在mid的右边。
low = mid + 1
(2)array[mid] == array[high]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1],此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试 ,
high = high - 1
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
high = mid
注意这里有个坑:如果待查询的范围最后只剩两个数,那么mid 一定会指向下标靠前的数字
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid - 1,就会产生错误, 因此high = mid
但情形(1)中low = mid + 1就不会错误
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int low = 0 ; int high = array.length - 1;    
        while(low < high){
            int mid = low + (high - low) / 2;         
            if(array[mid] > array[high]){
                low = mid + 1;
            }else if(array[mid] == array[high]){
                high = high - 1;
            }else{
                high = mid;
            }    
        } 
        return array[low];
    }
}
编辑于 2017-08-01 13:06:40 回复(209)

JavaScript

看了排行第一大佬 念润 的解法和其回复内泥点药丸 的补充,得到如下解法:

function minNumberInRotateArray(rotateArray) {
    var left = 0,
        length = rotateArray.length,
        right = length - 1,
        mid;
    if (length == 0) { return 0; }
    while (rotateArray[left] >= rotateArray[right]) {
        if (rotateArray[left] == rotateArray[right]) {
            // 对left去重,使其指向最后一个重复的数字
            for (var i = left; i < right; i++) {
                if (rotateArray[left] != rotateArray[i]) {
                    left =i-1;
                    break;
                }
            }
            // 对right去重,使其指向最前一个重复的数字
            for (var i = right; i > left; i--) {
                if (rotateArray[right] != rotateArray[i]) {
                    right = i+1;
                    break;
                }
            }
        }

        if (right - left <= 1) {
            mid = right;
            break;
        }
        // 四舍五入取整数,否则得到的就是小数,会报错;
        mid = Math.round(left + (right - left) / 2);
        if (rotateArray[mid] >= rotateArray[left]) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return rotateArray[mid];
}
编辑于 2019-05-07 19:52:50 回复(2)
前方大坑!!
rotateArray.size() == 0时候返回一个0
这个设定极其不合理,无法区分是min=0还是出错了


递归代码:
class Solution {
    int findMin(vector<int> a, int first, int last) {
        if (first >= last) return a[last];
        int mid = (first + last) / 2;
        if (a[first] == a[last] && a[mid] == a[first]) {
            // linear search
            int min = a[first];
            for (int i = first + 1; i <= last; i++)
                min = a[i]<min ? a[i] : min;
            return min;
        }
        if (a[first] < a[last]) {
            return a[first];
        } else {
            if (a[mid] >= a[first]) {
                return findMin(a, mid + 1, last);
            } else {
                return findMin(a, first, mid);
            }
        }
    }
 
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int n = rotateArray.size();
        if (n == 0) return 0;
        return findMin(rotateArray, 0, n - 1);
    }
};

循环代码:
class Solution {  
public:
    int minNumberInRotateArray(vector<int> array) {
        if (array.size() == 0) return 0;
        int first = 0, last = array.size() - 1;
        int mid = (first + last) / 2;
        while (array[first] >= array[last]) {
            if (last - first == 1) return array[last];
            if (array[first] == array[mid] && array[mid] == array[last]) {
                // linear search
                int min = array[first];
                for (int i = first + 1; i <= last; i++)
                    min = array[i]<min ? array[i] : min;
                return min;
            }
             
            if (array[first] <= array[mid]) first = mid;
            else last = mid;

            mid = (first + last) / 2;
        }
        return array[first];
    }
};

编辑于 2015-07-27 14:12:26 回复(7)
package go.jacob.day0827.剑指offer系列;

public class 旋转数组的最小数字 {
    public int minNumberInRotateArray(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int len = array.length;

        int index1 = 0;
        int index2 = len - 1;
        int indexMid = index1;

        while (array[index1] >= array[index2]) {
            if (index1 == index2 - 1) {
                indexMid = index2;
                break;
            }
            indexMid = index1 + (index2 - index1) / 2;
            if (array[index1] <= array[indexMid]) {
                index1 = indexMid;
            } else if (array[indexMid] <= array[index2]) {
                index2 = indexMid;
            }
        }

        return array[indexMid];
    }


}

编辑于 2018-09-04 13:48:00 回复(2)
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
    if (array != null && array.length > 0) {
int index1 = 0;
int index2 = array.length - 1;
int indexMid = index1;

while (index1 <= index2) {
indexMid = (index1 + index2) / 2;

if (array[indexMid] == array[index2]
&& array[index1] == array[index2]) {

int min = array[0];
for (int i = 1; i < array.length; i++) {
if (min > array[i]) {
min = array[i];
}
}

return min;
}

else if (array[indexMid] > array[index1]) {
index1 = indexMid;
} else {
index2 = indexMid;
}
}

return indexMid;
} else {
return 0;
}
    }
已经通过
发表于 2015-08-15 17:46:48 回复(1)
class Solution {
public:
   int order_Search(vector<int> &array,int start,int end)
   {
       int min=array[start];
       for(int i=start+1;i<=end;i++)
       {
           if(array[i]<min)
               min=array[i];
       }
       return min;
   }
   int binary_Search(vector<int> &array,int start,int end)
 {
    if(end-start<=1)
        return array[start]<=array[end]?array[start]:array[end];
    int mid=start+((end-start)>>1);
    if(array[mid]>array[start])
    {
        if(array[start]>=array[end])
            return binary_Search(array,mid+1,end);
        else
            return array[start];
    }
    else if(array[mid]==array[start])
 	{
        if(array[start]>array[end])
            return binary_Search(array,mid+1,end);
        else if(array[start]==array[end])
        {
            return order_Search(array,start,end);
        }
        else
            return array[start];
    }
    else
        return binary_Search(array,start+1,mid);
}
 
int minNumberInRotateArray(vector<int> rotateArray) {
    int length=rotateArray.size();
    if(length==0)
            return 0;
        if(length==1)
            return rotateArray[0];
        return binary_Search(rotateArray,0,length-1);
  }
};

编辑于 2015-04-07 21:28:32 回复(0)
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return  0
        else:
            return min(rotateArray)

编辑于 2016-08-24 21:42:14 回复(7)
//折半查找--每次折半,时间复杂度logn
//本来写了个循环只需判断下降沿--Array[i]>Array[i+1]就行了,
考虑时间复杂度为n,折半查找会好点
class Solution {
public:
    int minNumberInRotateArray(vector<int> Array) {
        if(Array.empty())
            return 0;
        int st=0;
        int end=Array.size()-1;
        int mid=(st+end)/2;
        while(st<end){
            if(Array[mid]==Array[st])
                return Array[mid+1];
            else if(Array[mid]>Array[st])
                st=mid;
            else
                end=mid;
            mid=(st+end)/2;
        }
        return 0;
    }
};

发表于 2016-07-05 20:26:42 回复(2)
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # 可以使用min()函数, 但是在不适用min函数的情况下,思路应该是二分查找
        # 下面使用 递归实现2分查找,其中递归的时候必须使用return!!! 不然会返回none
        # write code here 
        start = 0
        end = len(rotateArray) - 1
        mid = int((start + end) / 2)
        if len(rotateArray) == 2:
            if rotateArray[0]>rotateArray[1]:
                return rotateArray[1]
            else:
                return rotateArray[0]

        elif rotateArray[mid] > rotateArray[end]:
            return self.minNumberInRotateArray(rotateArray[mid:end + 1])
        elif rotateArray[mid] < rotateArray[start]:
            return self.minNumberInRotateArray(rotateArray[start:mid + 1])

发表于 2018-04-17 21:38:33 回复(4)
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length==0)return 0;
        int L=0,R=array.length-1;
		for(int i =0;i<R;i++){
            if(array[i]>array[i+1])
                return array[i+1];
        }
        return array[0];
    
    }
}

编辑于 2015-09-11 16:51:14 回复(2)
二分法思路:分别比较arr[mid]与arr[first](数组第一个元素)、arr[last](数组最后一个元素)的大小,
arr[mid]>arr[last],说明最小值在mid右边,arr[mid]<arr[first],说明最小值在mid左边;
修改first,last循环迭代,当只剩最后两个元素是得到最小值。
function minNumberInRotateArray(rotateArray) {     // write code here     if(rotateArray.length === 0){         return 0;     }     var first = 0;     var last = rotateArray.length - 1;     var mid = Math.ceil((first + last) / 2);;     while(first + 1 < last){         if(rotateArray[mid] > rotateArray[last]){             first = mid;         }         if(rotateArray[mid] < rotateArray[first]){             last = mid;         }         mid = Math.ceil((first + last) / 2);     }     return rotateArray[mid]; }

编辑于 2018-08-30 10:45:30 回复(1)
//从两端向中间进行遍历
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array==null){
              return 0;
          }
        
        int minHand=0;
        int lHand=0;
        int rHand=array.length-1;
        
        while(lHand<rHand){
            if(array[lHand]<=array[lHand+1]){
                lHand=lHand+1;
            }else{
                minHand=lHand+1;
                break;
            }
            
            if(array[rHand]>=array[rHand-1]){
                rHand=rHand-1;
            }else{
                minHand=rHand;
                break;
            }
        }
        
        return array[minHand];
    }
}
发表于 2017-01-04 11:19:25 回复(1)
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
   	  if(array.length==0)return 0;
		int start = 0;
		int end = array.length - 1;
		if(array[start]<array[end]) return array[start];
		while(start !=end -1){
			int mid = (start + end)/2;
			if(array[start] == array[end]&&array[mid] == array[start]){
				return minInOrder(array,start,end);
			}	
			if(array[mid]>=array[start]){
				start = mid;
			}else if(array[mid]<=array[end]){
				end = mid;
			}
		}
		return array[end];
    }
    private static int minInOrder(int[] array, int start, int end) {
		int result = array[start];
		for(int i =start +1;i<=end;i++){
			if(result>array[i]){
				result = array[i];
			}
		}
		return result;
	}
}

发表于 2016-05-13 15:50:35 回复(0)
import java.util.ArrayList;
import java.lang.Math;
public class Solution {
    public int minNumberInRotateArray(int[] array) {
int left=0;
        int right=array.length-1;
        int mid=1;
        if(array==null){
            return 0;
        }
        while(array[left]>array[right]){
            if(left-right<=1){
                mid=right;
                break;
            }
            
            mid=(left+right)/2;
            if(array[left]<=array[mid]){
                left=mid;
            }else if(array[right]>=array[mid]){
                right=mid;
            }
        }
        return array[mid];
    }
    
    public static void main(String[] args){
        Solution st=new Solution();
        int[] array={3,4,5,1,2};
        System.out.println(st.minNumberInRotateArray(array));
    }
}
在eclipse中编译都过了,不知为何在线无法运行
发表于 2015-04-08 13:30:44 回复(6)
这题就算用二分,最坏情况下也是O(n)啊(所有元素都相同),为啥题目写着O(lgn),太扯淡了,误人子弟!
发表于 2022-05-02 16:24:14 回复(0)
旋转数组特征: 原来数组为[a b] [c d] 且单调递增。
旋转后:[c d] [a b] 括号内的数递增, [a, b] < [c d],而本题所求的为a。

使用二分法来寻找
1. 若mid == r 则r--
2. 若mid < r 则说明mid落在(c d) 中的,且mid可以取到a 故为 r = mid 而不是mid - 1
3. 若mid > r 则说明mid落在(a, b)中的,且mid不可能取到a, 所以 l = mid + 1 而不是mid
循环结束都是 L == R 这个时候返回L 或 R均可

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int l = 0, r = rotateArray.size() - 1;
        while(l < r) {
            int mid = l + r >> 1;
            if (rotateArray[mid] == rotateArray[r]) r--;
            else if (rotateArray[mid] < rotateArray[r]) r = mid;
            else l = mid + 1;
        }
        return rotateArray[l];
    }
};  
发表于 2022-01-26 21:35:11 回复(0)
这题需要二分查找么?
class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # write code here
        small = rotateArray[0]
        temp = small
        for ind, val in enumerate(rotateArray):
            if val < temp:
                return val
            temp = val
        return small


发表于 2022-01-19 15:07:15 回复(0)
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    // write code here
    int i=1;
    int a,b,c;
    a=rotateArray[0];
    while(i<rotateArrayLen){
        b=rotateArray[i];
        if(a<b){c=a;}
        else{c=b;}
        i++;
        a=c;
    }
    return c;
}
发表于 2021-11-14 22:12:14 回复(1)
Java 递归+二分
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int ret,ret1 = 0;
        //if (array.length==0)return 0;
        if (array.length==1)return array[0];
        if (array.length==2){
            if(array[0]>array[1])return array[1];
            else return array[0];
        }
        if (array[0]<array[array.length-1])return array[0];
        if (array[0]>array[array.length/2])ret = minNumberInRotateArray(Arrays.copyOfRange(array,0,array.length/2+1));
        else if (array[0]<array[array.length/2])ret = minNumberInRotateArray(Arrays.copyOfRange(array,array.length/2,array.length));
        else {
            ret = minNumberInRotateArray(Arrays.copyOfRange(array,0,array.length/2+1));
            ret1 = minNumberInRotateArray(Arrays.copyOfRange(array,array.length/2,array.length));
            if(ret>ret1)return ret1;
        }
        return ret;
    }
}


发表于 2021-11-10 00:05:23 回复(0)
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
     //使用一个数标记最小数
     int min= array[0];
     for(int i=0;i<array.length;i++){
         //如果array[i]比min还小,进行替换
            if(array[i]<min){
                min=array[i];
            }
      }
        return min;
    }
}

发表于 2021-10-29 18:07:16 回复(0)