旋转数组的最小数字_

推荐

念润

思路

剑指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)

FINACK

采用二分法解答这个问题，

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 回复(210)

JavaScript

一只骑单车的猫

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)

fuyufjh

前方大坑！！

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)

JacobGo！

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)

yellow0is0me

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)

crisy1991

//折半查找--每次折半，时间复杂度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)

Python

最小森林

# -*- 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)

Lwan

//从两端向中间进行遍历

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)

noMercy

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)

_Moine

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)

牛客523674585号

这题就算用二分，最坏情况下也是O(n)啊（所有元素都相同），为啥题目写着O(lgn),太扯淡了，误人子弟！

发表于 2022-05-02 16:24:14 回复(0)

C++

Noah.Suming

旋转数组特征：原来数组为[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)

Python 3

passway

这题需要二分查找么？

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)

C

赶紧离职

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

陈明燊

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)

牛客675471006号

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)

Java

牛客774608432号

    public int minNumberInRotateArray(int [] array) {
        int l = 0;
        int r = array.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (array[mid] < array[r]) {
                r = mid;
            } else if (array[mid] > array[r]) {
                l = mid + 1;
            } else {
                r -= 1;
            }
        }
        return array[l];
    }

发表于 2021-10-04 20:15:43 回复(0)

JavaScript Node

牛客67815066号

简洁的JavaScript (二分):

function minNumberInRotateArray(rotateArray)
{
    // write code here
    if (rotateArray.length === 0) return;
    if (rotateArray.length === 1) return rotateArray[0];
    if (rotateArray.length === 2) return Math.min(rotateArray[0], rotateArray[1]);
    let mid_index = Math.floor(rotateArray.length / 2);
    let mid = rotateArray[mid_index];
    let leftmost = rotateArray[0];
    let rightmost = rotateArray[rotateArray.length - 1];
    let left = rotateArray.slice(0, mid_index + 1);
    let right = rotateArray.slice(mid_index + 1);
    if (leftmost > mid) return minNumberInRotateArray(left);
    else if (mid > rightmost) return minNumberInRotateArray(right);
    else return Math.min(minNumberInRotateArray(left), minNumberInRotateArray(right))
}

发表于 2021-09-28 02:13:48 回复(1)

Javascript

Active_Waylon

// 你可以使用O(logN)的时间复杂度通过该题吗?
function minNumberInRotateArray(rotateArray)
{
    // write code here
    // 解法1 暴力法
    // return Math.min(...rotateArray);
    
    // 解法2 二分法
    
    let n = rotateArray.length-1;
    if(n<0) {
        return 0;
    }
    //  二分查找，
    // 要达到二分性质，需要使前半段 nums[i] >= nums[0] 后半段 nums[i]<nums[0]
    // 去除第二段末尾与nums[0]相等的元素
    while(rotateArray[n] == rotateArray[0] && n > 0) {
        n--;
    }
    if(rotateArray[n] >= rotateArray[0]) {
        return rotateArray[0];
    }
    // 开始二分
    let left = 0;
    let right = n;
    while(left < right) {
        let mid = left+right >> 1;
        if(rotateArray[mid] < rotateArray[0]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return rotateArray[right];
}

发表于 2021-09-14 23:17:14 回复(0)

旋转数组的最小数字

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题