leetcode力扣153题.寻找旋转排序数组中的最小值

淩亂°似流年 2023-03-01 12:22 153阅读 0赞

**题目：**

> 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
> 
> ( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。  
>   
> 请找出其中最小的元素。
> 
> 你可以假设数组中`不存在重复元素`。
> 
> 示例 1: `输入: [3,4,5,1,2]`  
> 输出: 1  
> 示例 2: `输入: [4,5,6,7,0,1,2]`  
> 输出: 0

**分析：**

可以用的方法有三种：

1.  无脑遍历；
2.  排序；
3.  二分。

显然时间复杂度最小的就是二分法。

### 一、使用模板的写法 ###

模板总结以及解释链接：  
[二分查找简介、二分查找的三类模板总结][Link 1]

class Solution {
        
        public int findMin(int[] nums) {
        
            int i = 0;
            int j = nums.length-1;
            while( i<j ){
        
                int mid = (i+j)/2;
                if( nums[mid]>nums[j] ){
        //j也可以替换成nums.length-1，但是j虽然变化但是在变小，所以无妨
                    i = mid+1;
                }else{
        
                    j = mid;
                }
            }
            return nums[i];
        }
    }

因为这个题目是需要考虑，`当前位置` 和 `右边的位置`，如果当前位置大于右边位置，就是答案。

所以很自然的使用模板 2 .

### 二、不使用模板 ###

在没有模板的情况下，我们可能需要在二分的过程考虑的更多。  
![在这里插入图片描述][20200725110208248.png]

那就是，对于一个位置，要考虑自身，以及自身右边的位置。  
他可能处于左边上升区，右边上升区。查找的 mid 如果是答案，他可能是最小值，也可能是最小值前面的那个最大值。

class Solution {
        
        public int findMin(int[] nums) {
        
            if (nums.length == 1) {
        
                return nums[0];
            }
            int i=0, j=nums.length - 1;
    
            if (nums[right] > nums[0]) {
        
                return nums[0];
            }
    
            while ( i <= j ) {
        
                int mid = i + (j-i) / 2;
                if (nums[mid] > nums[mid + 1]) {
        
                    return nums[mid + 1];//左大右小
                }
                if (nums[mid - 1] > nums[mid]) {
        
                    return nums[mid];//左大右小
                }
    
                //不存在左大右小了，说明在各自的增区间里
                if (nums[mid] > nums[0]) {
        
                    i = mid + 1;
                } else {
        
                    j = mid - 1;
                }
            }
            return -1;
        }
    }

看到这个代码，应该更能理解模板 2 的优越性。

[Link 1]: https://blog.csdn.net/weixin_42092787/article/details/107569789
[20200725110208248.png]: /images/20230208/f5a01c9e0ca3472191f3e6a0138595bf.png