VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 154. 寻找旋转排序数组中的最小值 II

Posted on Edited on In , ,

摘要：
二分查找经典应用，当数组中包含重复数字时，事情发生了变化。

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5]
输出: 1

示例 2：

输入: [2,2,2,0,1]
输出: 0

说明：

二分查找

这道题和 寻找旋转排序数组中的最小值 的区别就在于折叠数组中可能存在重复。

什么时候会产生影响呢？那就是当折叠点在原数组中某一数字相同段内时，折叠之后，数组首尾相同。那么，如果 mid 更新到与数组首尾相同的数字时，我们无法利用二分查找所依赖的 性质 确定 mid 是在左半边还是右半边。

那么，解题思路就是：

  • 先特判非单调递减情况，排除原数组折叠点在数组下标范围外的情况。
  • 再特判折叠数组首尾相同的情况，方法是移动右指针向左直到和左端点不同为止。那么此时又有两种情况：
  1. 右半边全为与左端点相同的数字，那么此时右指针移到了左半边， nums[hi] > nums[0]
  2. 右半边不全是与左端点相同的数字，那么此时右指针依然在右半边， nums[hi] < nums[0]

另外可以想一下，如果折叠数组数组完全相同，也就是最坏的情况，会怎么样。
那必然是最终右指针左移时与左指针相遇，进行一次常规二分直接得出答案。当然也可以在进入常规二分之前特判一下，都无所谓。
最坏的情况下，复杂度为 $O(N)$，平均的情况下，复杂度为 $O(logn)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 执行用时: 4 ms
// 内存消耗: 11.8 MB
class Solution {
public:
    int len;
    int findMin(vector<int>& nums) {
        len = nums.size();

        int lo = 0, hi = len - 1;

        // 特判非递减情况（折叠点不在原数组下标范围内）
        if (nums[hi] > nums[lo]) return nums[lo];

        // 特判折叠点在重复数字中的情况（折叠后数组首尾相同）
        for (; lo < hi && nums[hi] == nums[0]; hi--); 

        // 此时存在两种情况，一是右半边还有数字，二是右半边无数字
        // 如果是右半边有数字，那么右半边递增，全部数字小于num[0];
        // 如果右半边没有数字，也就是说hi到了左半边，直接返回nums[0];
        if (nums[hi] > nums[0]) return nums[lo];

        // 常规情况，和153题解法一致
        for (; lo < hi;) {
            int mid = lo + hi >> 1;
            if (nums[mid] >= nums[0]) lo = mid + 1;
            else hi = mid;
        }
        return nums[lo];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 执行用时: 0 ms
// 内存消耗: 38.3 MB
class Solution {
    int len;
    public int findMin(int[] nums) {
        len = nums.length;

        int lo = 0;
        int hi = len - 1;
        
        if (nums[hi] > nums[lo]) return nums[0];

        for (; lo < hi && nums[lo] == nums[hi]; hi--);

        if (nums[hi] > nums[lo]) return nums[0];

        for (; lo < hi;) {
            int mid = lo + hi >> 1;
            if (nums[mid] >= nums[0]) lo = mid + 1;
            else hi = mid;
        } 

        return nums[lo];
    }
}

原题链接： LeetCode 154. 寻找旋转排序数组中的最小值 II