bugCat's Blog

毛的感情的程序猿

0%

旋转排序数组小结

发表于 更新于 分类于
本文字数： 6.6k 阅读时长 ≈ 6 分钟

旋转排序数组小结

在刷LeetCode的时候遇到了一些关于旋转排序数组的问题，记录一下。

33. 搜索旋转排序数组

题目描述

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

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

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

1
2
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

1
2
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

二分法思路比较简单，因为做过很多次了

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
31
32
33
34
35
36
37
38
class Solution {
    public int search(int[] nums, int target) {
        if (nums==null||nums.length==0) {
            return -1;
        }
        int left = 0;
        int right = nums.length-1;
        int mid = 0;

        //使用二分法解决
        //这里是<=号，为了防止nums.length=1的情况
        while (left<=right) {
            mid = (left+right)/2;
            if(nums[mid]==target)return mid;
            //这里也是<=号，为了处理类似于left=right=nums.length的情况
            //此时mid=nums.length,如果这路不是<=,就会进入下面nums[mid+1]进行判断，可能出现越界
            if (nums[left]<=nums[mid]) {
                //说明 从 left到mid都为有序
                if (nums[left]<=target && nums[mid]>target) {
                   //说明 target在left到mid
                   right = mid-1;
                } else {
                    //说明 target在left到mid
                    left = mid+1;
                }
            }else{
                //说明 从 mid+1到right为有序
                if (nums[mid+1]<=target && nums[right]>=target) {
                    //说明在 mid+1到right
                    left = mid+1;
                } else {
                    right = mid-1;
                }
            }
        }
        return -1;
    }
}

81.搜索旋转排序数组II

题目描述

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

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

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

1
2
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

示例 2:

1
2
3
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
进阶:

这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

因为在这种情况下出现了元素重复的情况，我们可以把问题分为三类，转载自https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/solution/zai-javazhong-ji-bai-liao-100de-yong-hu-by-reedfan/

  • 第一类
    101111和 111101这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
  • 第二类
    22 33 44 55 66 77 11这种，也就是 nums[start] < nums[mid]。此例子中就是 2 < 5；
    这种情况下，前半部分有序。因此如果 nums[start] <=target<nums[mid]，则在前半部分找，否则去后半部分找。和上面那题相同
  • 第三类
    66 77 11 22 33 44 55 这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2；
    这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找，否则去前半部分找。和上面那题相同

大致代码和上面相同，但是出现一个判断,当然这题特殊情况下并不能实现完全的二分，最差的情况还是o(n)

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
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public boolean search(int[] nums, int target) {
        if (nums==null||nums.length==0) {
            return false;
        }
        int left = 0;
        int right = nums.length-1;
        int mid = 0;

        //使用二分法解决
        while (left<=right) {
            mid = (left+right)/2;
            if(nums[mid]==target)return true;
            //多这个判断,将非选择答案去掉
            if (nums[left] == nums[mid]) {
                left++;
                continue;
            }

            if (nums[left]<nums[mid]) {
                //说明 从 left到mid都为有序
                if (nums[left]<=target && nums[mid]>target) {
                   //说明 target在left到mid
                   right = mid-1;
                } else {
                    //说明 target在left到mid
                    left = mid+1;
                }
                
            }else{
                //说明 从 mid+1到right为有序
                if (nums[mid+1]<=target && nums[right]>=target) {
                    //说明在 mid+1到right
                    left = mid+1;
                } else {
                    right = mid-1;
                }
            }
        }
        return false;
    }
}

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

题目描述

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

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

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

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

示例 2:

1
2
输入: [4,5,6,7,0,1,2]
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

按照我的思路可以这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        int minNum = Integer.MAX_VALUE;
        while (left <= right) {
            mid = (left+right)/2;
            if (nums[left] <= nums[mid]) {
                // 说明从 left 到 mid为有序
                minNum = Math.min(minNum, nums[left]);
                left = mid + 1;
            } else {
                // 说明从 mid 到 right为有序
                minNum = Math.min(minNum, nums[mid]);
                right = mid-1;
            }
        }
        return minNum;
    }
}

但是其实这题就是旋转旋转的最小值，其实也可以理解为寻找乱序的一边，因为乱序的一边里面肯定有最小值,但是这里面有许多小细节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        //这里是 < 号，因为在nums.length==1的情况下
        while (left < right) {
            mid = (left + right) / 2;
            //注意这路是拿 mid 和 right进行比较，后面会有解释
            if (nums[mid] < nums[right]) {
                // 说明从 mid 到 right为有序
                right = mid;
            } else {
                // 说明从 left 到 mid为有序
                left = mid+1;
            }
        }
        return nums[left];
    }
}

上面我们看到的细节是拿 mid 和 right进行比较这个其实也是有原因的。我们主要拿left,mid,right进行比较，会出现几种情况：

  1. 如果未进行旋转，整个数组有序。nums[left]<nums[mid]<nums[right]。此时是都有序，最小值在最左边，可以收缩右边界
  2. 进行了旋转，如果nums[left]>nums[mid],nums[mid]<nums[right],那说明左半部分是无序的，右半部分是有序的，那最小值肯定在左半部分，所有应该收缩右边界。eg:[8,9,1,2,3,4,5,6,7]这种情况
  3. 进行搜索，如果nums[left]<nums[mid],nums[mid]>nums[right],说明左半部分是有序的，右半部分是无序的，那最小值在右半部分，左边界应该收缩。eg:[4,5,6,7,8,9,1,2,3]

在这几种情况当中，我们发现如果使用left和mid进行比较的话，是分不出1，3这两种情况，而我们使用mid和right进行比较的话会发现1，2变成了一种情况，能够比较好的区分出来。所有使用mid 和 right进行比较。

还有一点有疑惑的地方就是为啥让right = mid为什么不是mid-1。其实这个是为了防止出现类似于[3,1,2]这种情况，因为刚好mid到right就是刚刚好旋转的部分，这样我们保留住mid就可以让左半边确保一定是无序的。

另外需要说明的是因为left不可能等于right，所以left<=mid<right，right=mid和left=mid+1是一定会让区间发生变化。

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

题目描述

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

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

请找出其中最小的元素。

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

示例 1：

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

示例 2：

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

说明：

  • 这道题是 寻找旋转排序数组中的最小值 的延伸题目。
  • 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

思路上承接上题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (nums[mid] < nums[right]) {
                // 说明从 mid+1 到 right为有序
                right = mid;
            } else if(nums[mid]>nums[right]){
                // 说明从 left 到 mid为有序
                left = mid+1;
            }else{
                right--;
            }
        }
        return nums[left];
    }
}

多了一种情况nums[mid]== nums[right],这个类似于81题的思路，可能出现101111和 111101这两种情况，因为无法确定我们只能让righ—，让它变成153题。

总结

这些旋转数组典型的特征就是二分搜索。发现了二分搜索几个比较重要的点：

  • 一般是比较left,mid,right三个位置的数然后再想办法收缩区间，一般来说每次都收缩一半。
  • 退出条件是while (left < right)还是while (left <=right)其实差别一般来说不大，
    • 当退出条件是while (left < right)时，说明退出条件为left==right,所以如果是类似搜索target之类的题目，最后比较一下left就行，如果是找位置则直接返回left就可以。
    • 当退出条件是while (left <=right)时，退出条件只有left>right，left==right会在里面进行比较，所以一般来说答案在while循环里面就进行了比较，不需要出来再进行什么处理了。
  • 是比较nums[left]和nums[mid]还是比较nums[mid]和nums[right]需要推敲，但是一般情况下是不影响
  • left或者right其中之一在比较后一定需要进行数值上的更改（mid+1或者mid-1），不然可能陷入死循环。
    • 当退出条件是left<right时，left<=mid<right,所以righ需要更改t时，可以赋值为mid，但是left更改必须为mid+1
    • 当退出条件是left<=right时，left<=mid<=right,所以righ需要更改t时不能赋值为mid，必须为mid-1，而left必须为mid+1；
  • 当退出条件是left<=right时，并且需要比较nums[mid+1]和nums[right]时，需要注意mid+1可能会越界的问题

参考：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/