Leetcode: 寻找旋转排序数组中的最小值

淡淡的烟草味﹌ 2022-11-17 03:49 157阅读 0赞

Leetcode第153道题: 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = \[0,1,2,4,5,6,7\] 在变化后可能得到：  
若旋转 4 次，则可以得到 \[4,5,6,7,0,1,2\]  
若旋转 4 次，则可以得到 \[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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素

示例:

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

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

思路:在二分查找的每一步中，左边界为 low，右边界为 high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素nums\[pivot\] 与右边界元素 nums\[high\] 进行比较，可能会有以下的三种情况：

第一种情况是 nums\[pivot\]<nums\[high\]。如下图所示，这说明nums\[pivot\] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70]  
第二种情况是nums\[pivot\]>nums\[high\]。如下图所示，这说明nums\[pivot\] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 1]  
由于数组不包含重复元素，并且只要当前的区间长度不为 1，pivot 就不会与high 重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在 nums\[pivot\]=nums\[high\] 的情况。

class Solution { 
        public int findMin(int[] nums) { 
            int low = 0;
            int high = nums.length - 1;
            while (low < high) { 
                int pivot = low + (high - low) / 2;
                if (nums[pivot] < nums[high]) { 
                    high = pivot;
                } else { 
                    low = pivot + 1;
                }
            }
            return nums[low];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70]: /images/20221022/ad1e12967f6b47b2b4fd14d97674e139.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU4NjcxMw_size_16_color_FFFFFF_t_70 1]: /images/20221022/9d6b62d03c44448b80ac9424dda05276.png