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

1442个回答

添加回答
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length==0||array==null){
            return 0;
        }
        int min=99999;
        for(int i=0;i<array.length;i++){
            if(array[i]<min){
                min=array[i];
            }
        }
        return min;
    }
发表于 2018-05-16 20:50:11 回复(0)
更多回答
推荐
思路

剑指Offer中

   查看全部
编辑于 2015-08-18 23:34:39 回复(80)
采用二分法解答这个问题,
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 回复(132)
三种方法,
1、最笨的一种:
    遍历整个数组,找出其中最小的数。这样肯定拿不到offer
2、稍微优化:
   public int minNumberInRotateArray(int[] array) {
		if (array.length == 0)
			return 0;
		for (int i = 0; i < array.length - 1; i++) {
			if (array[i] > array[i + 1])
				return array[i + 1];
		}
		return array[0];
	} 
3、二分查找:
public static int minNumberInRotateArray(int[] array) {
		if (array.length == 0)
			return 0;
		int left = 0;
		int right = array.length - 1;
		int middle = -1;
		while (array[left]>=array[right]) {
			if(right-left==1){
				middle = right;
				break;
			}
			middle = left + (right - left) / 2;
			if (array[middle] >= array[left]) {
				left = middle;
			}
			if (array[middle] <= array[right]) {
				right = middle;
			}
		}
		return array[middle];
	}

发表于 2017-01-09 10:57:17 回复(26)
//C++ 二分法
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if (rotateArray.empty()) return 0;
        int left = 0, right = rotateArray.size() - 1;
        while (left < right) {
            //确认子数组是否是类似1,1,2,4,5,..,7的非递减数组
            if (rotateArray[left] < rotateArray[right]) return rotateArray[left];
            
            int mid = left + (right - left) / 2;
            //如果左半数组为有序数组
            if (rotateArray[left] < rotateArray[mid])
                left = mid + 1;
            //如果右半数组为有序数组
            else if (rotateArray[mid] < rotateArray[right])
                right = mid;
            //否则,rotateArray[left] == rotateArray[mid] == rotateArray[right]
            else {
                ++left;
            }
        }
        return rotateArray[left];
    }
};


发表于 2018-05-17 10:48:25 回复(5)
XD头像 XD
/*把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。*/
根据题意说明是一个递增数组的旋转,所以如题所示【3,4,5】,【1,2】还是局部递增的,在这种的数组中查找,一般选择二分的方法;基本模型有了,下面试着分析:
1.先取出中间的数值,和最后一个比较5>2 说明mid之前的某些部分旋转到了后面,所以下次寻找 low = mid+1 开始;
2.取出的中间值要是小于high,说明mid-high之间都应为被旋转的部分,所以最小应该在mid的前面,但是也有可能当前的mid 就是最小的值 所以下次需找的应该 从mid开始,也即high = mid 开始
3.当*mid == *high的时候,说明数组中存在着相等的数值,可能是这样的形式 【2,2,2,2,1,2】所以应该选择的high 应该递减1 作为下次寻找的上界。
参考代码如下:
  int minNumberInRotateArray(vector<int> rotateArray) {  
    size_t len = rotateArray.size();
    if(len == 0)
        return 0;
    if(len == 1)
        return rotateArray[0];
    vector<int>::iterator low = rotateArray.begin();
    vector<int>::iterator mid;
    vector<int>::iterator high = rotateArray.end()-1;
    while(low <= high)
    {
        //防止迭代器失效
        mid = low + (high - low)/2;
        if(*mid >*high)
        {
            low = mid + 1;
        }
        else if(*mid < *high)
        {
            high = mid;
        }
        else
        {
            high = high-1;
        }
        if(low >= high)
        {
            break;
        }
    }
        return *low;
    }  

发表于 2015-08-11 14:03:13 回复(5)
此题比较扯的。但题目还是不错。
比较扯的原因:
1.当数组为空的时候,测试用例需要返回0,我返回-1,结果没通过。
2.明明题目说是递增数列,测试用里面竟然有非递减数列。

正确做法需要分为:
1.数组为空
2.部分旋转,例如由(1,2,3,4,5)旋转为(3,4,5,1,2),此时只需要遍历数组,找到当前数比前面的数小的数即可。
3.完全旋转,例如由(1,2,3,4,5)旋转为(1,2,3,4,5),此时第一个数最小。
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {

        //数组为空时
        if(rotateArray.size() == 0)
            return -1;
        //前部分数据旋转
        for(int i = 0; i < rotateArray.size() - 1; i++){
            if (rotateArray[i] > rotateArray[i + 1])
                return rotateArray[i + 1];
        }

        //全部数据旋转,相当于没有旋转,最小数即为第一个数
        return rotateArray[0];
    }
};

发表于 2015-05-13 14:43:11 回复(32)
public class Solution {
 /*
 * 传进去旋转数组,注意旋转数组的特性:
 * 1.包含两个有序序列
 * 2.最小数一定位于第二个序列的开头
 * 3.前序列的值都>=后序列的值
 * 定义把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
 * ^_^这个旋转思想是很经典的
 * 旋转数组实例:
 * {123456}旋转后{456123}
 */
 
 //用到了快速排序的快速定位范围的思想,
 public int minNumberInRotateArray(int [] array) {

 if(array==null||array.length==0){  return 0;
 }
 int low=0;
 int up=array.length-1;
 int mid=low;
 
 // 当low和up两个指针相邻时候,就找到了最小值,也就是
 //右边序列的第一个值
 
 while(array[low]>=array[up]){
 if(up-low==1){
 mid=up;
 break;
 }
 //如果low、up、mid下标所指的值恰巧相等
 //如:{0,1,1,1,1}的旋转数组{1,1,1,0,1}
 if(array[low]==array[up]&&array[mid]==array[low])
 return MinInOrder(array);
    mid=(low+up)/2;
 //这种情况,array[mid]仍然在左边序列中
 if(array[mid]>=array[low])
 low=mid;//注意,不能写成low=mid+1;
 //要是这种情况,array[mid]仍然在右边序列中
 else if(array[mid]<=array[up])
 up=mid;
 }
 
 return array[mid];
    
    }
 private int MinInOrder(int[] array) {
 // TODO Auto-generated method stub
 int min =array[0];
 for(int i=1;i<array.length;i++){
 if(array[i]<min){
 min=array[i];
 
 }
 }
 return min;
 }
 public static void main(String[] args) {
 
 }

}


编辑于 2015-04-11 17:55:45 回复(3)
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        for i in range(len(rotateArray)):
            if rotateArray[i+1] < rotateArray[i]:
                return rotateArray[i+1]
        return 0

发表于 2018-03-20 16:05:21 回复(0)

python solution:

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        return min(rotateArray)
发表于 2017-10-07 19:14:16 回复(15)
前方大坑!!
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 回复(5)
Python方法大总结
方法一:直接min函数,有点像开挂
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        else:
            return min(rotateArray)
方法二:先sort排序
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        else:
            rotateArray.sort()
            return rotateArray[0]
方法三:二分查找
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        length = len(rotateArray)
        if length == 0:
           return 0
        elif length == 1:
            return rotateArray[0]
        else:
            left = 0
            right = length - 1
            while left < right:
                mid = (left + right)/2
                if rotateArray[mid] < rotateArray[j]:
                    right = mid
                else:
                    left = mid+1
            return rotateArray[i]
方法四:比较
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        length = len(rotateArray)
        if length == 0:
           return 0
        elif length == 1:
            return rotateArray[0]
        else:
            for i in range(length-1):
                if rotateArray[i] > rotateArray[i+1]:
                    return rotateArray[i+1]
            return rotateArray[length-1]
人生苦短,我用Python
发表于 2016-08-27 14:51:27 回复(1)
//折半查找--每次折半,时间复杂度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)
我这个代码感觉挺简单的,测试通过。求大家挑挑毛病
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()==0){
            return 0;
        }
        int min = rotateArray[0];
        for(int i=1;i<rotateArray.size();i++){
            if(rotateArray[i]<min){
                min = rotateArray[i];
                break;
            }
        }
        return min;
    }
};

发表于 2015-05-04 23:51:41 回复(19)
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0)
			return 0;
        int i = 0;
		while (i < array.length - 1 && array[i] <= array[++i])
			;
		return i == array.length - 1 ? array[0] : array[i];
    }
}
我的思路是:首先数组长度为零时,返回零,因为测试要求这样。然后有一个特殊情况是没有旋转,那么返回array[0],其次一般情况while一直循环,知道后面的数 < 前面的数停止,这个数就是我们要找的。

发表于 2015-08-18 09:52:20 回复(3)
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)
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 回复(0)
二分法思路:分别比较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 回复(0)
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length==0)
            return 0;
        else 
            return partition(array,0,array.length-1);
    }
    //递归的目的是寻找乱序的子数组
    private int partition(int [] array,int start,int end){
        if( array[start] < array[end] || start == end )  //如果第一个元素小于最后一个元素,说明数组从头到尾都是非减的;如果只剩下一个元素,则直接返回
            return array[start];
        else {
            int mid=start+(end-start)/2;
            if( array[mid] < array[end]){    //如果中间值下于最后的值,说明后半部分为非减序列,所以在前半部分继续寻找;
                               //另外,之所以是mid而不是mid-1,是为了防止出现越界的情况,例如,array=[3,4],那么start=0,mid=0,end=1; (mid-1)等于-1,不可行
                return partition(array,start,mid);
            }else if(array[mid] == array[end]){    // 如果array=[1,0,1,1,1]或者[1,1,1,0,1],那没办法判断乱序子数组的位置,所以只能削减一步
                return partition(array,start,end-1);
            }else{                //如果中间值大于最后值,那么说明乱序的部分在后半段,所以在后半段寻找。可以使用mid+1是因为,中间值都比最后值大了,那还要它干嘛?
                return partition(array,mid+1,end);
            }
        }
    }
}
编辑于 2018-08-06 23:10:21 回复(0)
# -*- 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 回复(3)
其实就是二分查找,查找时分两种情况:
1、array[m] > array[r]:说明旋转后最小值在右区间
2、array[m] < array[r]:说明旋转后最小值在左区间
(l、r是待查找区间边界,m是区间中间位置)

class Solution {
public:
    int minNumberInRotateArray(vector<int> array) {
        //二分查找
        if(array.size()==0){
            return 0;
        }
        int l=0, r=array.size()-1;
        while(l<r){
            int m = (l+r)>>1;
            if(array[m] > array[r]){
                l = m+1;
            }else{
                r = m;
            }
        }
        return array[l];
    }
};
发表于 2018-02-01 20:27:37 回复(3)
//从两端向中间进行遍历
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)