153. 寻找旋转排序数组中的最小值

曾经终败给现在 2024-04-01 17:10 5阅读 0赞

### 153. 寻找旋转排序数组中的最小值 ###

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = \[0,1,2,4,5,6,7\] 在变化后可能得到：

*  若旋转 4 次，则可以得到 \[4,5,6,7,0,1,2\]
 *  若旋转 7 次，则可以得到 \[0,1,2,4,5,6,7\]

注意，数组 \[a\[0\], a\[1\], a\[2\], …, a\[n-1\]\] 旋转一次 的结果为数组 \[a\[n-1\], a\[0\], a\[1\], a\[2\], …, a\[n-2\]\] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

##### 示例 1： #####

> 输入：nums = \[3,4,5,1,2\]  
> 输出：1  
> 解释：原数组为 \[1,2,3,4,5\] ，旋转 3 次得到输入数组。

##### 示例 2： #####

> 输入：nums = \[4,5,6,7,0,1,2\]  
> 输出：0  
> 解释：原数组为 \[0,1,2,4,5,6,7\] ，旋转 4 次得到输入数组。

##### 示例 3： #####

> 输入：nums = \[11,13,15,17\]  
> 输出：11  
> 解释：原数组为 \[11,13,15,17\] ，旋转 4 次得到输入数组。

##### 提示： #####

*   n = = n u m s . l e n g t h n == nums.length n==nums.length
 *   1 < = n < = 5000 1 <= n <= 5000 1<=n<=5000
 *   − 5000 < = n u m s \[ i \] < = 5000 -5000 <= nums\[i\] <= 5000 −5000<=nums\[i\]<=5000
 *  nums 中的所有整数 互不相同
 *  nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

#### 思路：二分查找 ####

*  特殊情况，如果旋转次数为0或者刚好为数组的长度，则数组的最后一个数一定大于第一个数
 *  否则，数组的最后一个数一定小于第一个数，且最小值及其右边的值全都小于其左边的值
 *  所以，当 n u m s \[ m i d \] > = n u m s \[ 0 \] nums\[mid\] >= nums\[0\] nums\[mid\]>=nums\[0\]时，最小值一定在右边，此时 l = m i d + 1 l = mid + 1 l=mid\+1
 *  当 n u m s \[ m i d \] < n u m s \[ 0 \] nums\[mid\] < nums\[0\] nums\[mid\]<nums\[0\]时，最小值一定在左边或当前位置，此时 h = m i d h = mid h=mid

#### 代码：（Java） ####

public class min_rotate {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [] nums = {
        2,1};
    		System.out.println(findMin(nums));
    	}
    	public static  int findMin(int[] nums) {
        
    		int l = 0,h = nums.length - 1;
    		if(nums[0] < nums[h])
    			return nums[0];
    		while(l < h) {
        
    			int mid = l + (h - l) / 2;
    			if(nums[mid] >= nums[0]) {
        
    				l = mid + 1;
    			}else {
        
    				h = mid;
    			}
    		}
    		return nums[l];
        }
    }

##### 复杂度分析： #####

*  时间复杂度：时间复杂度为  O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)，其中 nnn 是数组  n u m s nums nums 的长度。在二分查找的过程中，每一步会忽略一半的区间，因此时间复杂度为  O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)。
 *  空间复杂度： O ( 1 ) O(1) O(1)。

##### 注：仅供学习参考！ #####

来源：[力扣][Link 1]

[Link 1]: https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/