剑指Offer-旋转数组的最小数字

约定不等于承诺〃 2022-03-02 16:12 202阅读 0赞

## 题目描述 ##

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

初步解题思路：一开始看题没看懂题的意义，也没注意是题目为输入非减排序数组，于是直接遍历数组，求最小值。  
进阶解题思路：注意到输入的是一个非减排序数组，则这个数组是由两段非减数列组合起来的，最小值一定是第二段数列的第一个元素（排除完全旋转）。  
**最优解：题目的初衷是使用二分法解决。**

> mid = low + (high - low)/2  
> 需要考虑三种情况：  
> (1)array\[mid\] > array\[high\]：此时最小数字一定在mid的右边。 **low = mid + 1**  
> (2)array\[mid\] == array\[high\]： 若有array类似为 \[1,0,1,1,1\]或者\[1,1,1,0,1\]，此时无法判断mid位置，所以只调整high的位置。 **high = high - 1**  
> (3)array\[mid\] < array\[high\]：此时最小数字要么是array\[mid\]要么在mid的左边。 **high = mid**

## Java初步解题 ##

import java.util.ArrayList;
    public class Solution {
        public int minNumberInRotateArray(int [] array) {
            if(array.length == 0)
                return 0;
            int min = array[0];
            for(int i=1;i<array.length;i++){
                if(array[i]<min)
                    min = array[i];
            }
            return min;
        }
    }

## Java进阶解题 ##

public class Solution {
    	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]; // 完全翻转
    	    } 
    }

## 最优解 ##

// 二分法思想
    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];
        }
    }