长大后想做什么？做回小孩！

0%

LeetCode——寻找旋转排序数组中的最小值I&II

发表于 分类于 Valine：
本文字数： 629

寻找旋转排序数组中的最小值 中等、寻找旋转排序数组中的最小值 II 困难

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

YPjr1H.png

思路一：二分法 O(n) 遍历本题没什么意义，题目给的是排序数组上搜索，二分法无疑。

重点在于如何判断 mid 的条件？

用 nums[mid] 和 nums[right] 进行比较 ，如果 nums[mid] > nums[right] ，说明 mid 的左边部分一定是一个严格升序区间(本题没有重复元素)，那么最小值一定在 mid 右边的部分；反之 nums[mid] < nums[right] 说明 mid 的右边是一个严格升序全进，最小值一定在 mid 的左边部分。

例如，[3,4,5,6,7,8,1,2]、[4,5,6,7,0,1,2]等等。。。

搜索的时候，搜索区间不断地向存在最小值的那一边收缩，搜索区间选择左闭右闭区间，搜索停止条件是搜索区间内只剩下一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    //left == right 时停止搜索,此时左闭右闭区间内剩余一个元素
    while (left < right) {
        int mid = left + ((right - left) >>> 1);
        if (nums[mid] > nums[right]) {
            //此时 mid 一定不是最小值,所以从搜索区间内删除
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

时间复杂度：O(logn)

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

YipnFP.png

思路一：二分法 和上一题的区别就在于本题的数组中存在重复元素。但是和上一题的思路变化并不大，只是本题需要再上一题的基础上，额外处理一下重复的元素。

处理重复元素是发生在nums[mid] == nums[right]的时候，需要剔除掉一个重复的元素， right 收缩一步即可将一个重复元素，从搜索区间中剔除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + ((right - left) >>> 1);
        if (nums[mid] == nums[right]) {
            //剔除一个重复元素
            right--;
        } else if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            right = mid;
        }
    }
    return nums[left];
}

时间复杂度：O(n) 最坏情况，所有元素都相同，只要区间右边界在步进，退化到O(n)。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github