旋转数组的最小数字

深碍√TFBOYSˉ_ 2024-02-19 13:06 14阅读 0赞

#### 文章目录 ####

*  题目描述
 *  代码
 *   *  最直观的代码
     *  二分法

## 题目描述 ##

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

## 代码 ##

### 最直观的代码 ###

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

### 二分法 ###

当arr\[mid\]>arr\[high\]时，low=mid+1;

当arr\[mid\]==arr\[high\]时， 情况未知，high–;

当arr\[mid\]< arr\[high\]时，high=mid;

import java.util.ArrayList;
    public class Solution {
        
        public static int minNumberInRotateArray(int[] array){
        
            if(array==null||array.length<0)
                throw new RuntimeException("invalid 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];
        }
    }