团灭四道搜索旋转排序数组题

发表于 | 分类于 | 本文总阅读量 次
字数统计: 2k | 阅读时长 ≈ 8

前言

在刷关于二分查找的算法题目时, 有一块内容是绕不过去的, 那就是旋转排序数组的题目.

我们知道, 在查找排序数组时往往采用二分查找的方法, 但是旋转排序数组只保留了区域性的排序, 这就让人比较头疼.通常的二分查找题目有两类, 一类是目标值查找, 即从数组中查找目标值, 返回其下标; 另一类考察的是边界, 这类题目更加灵活, 可能会考察第K大的数, 第一个重复出现的数等等.

结合了旋转数组之后, 就有了四道非常典型的题目, 他们是:

总体而言分别考察了目标值和最小值, 只是按是否存在重复的数又各拓展出一道题. 下面分别来解决.

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

题解

二分查找

首先，mid将数组分成前后两段：

如果nums[start]<=nums[mid]，则说明前半段是递增的

  • 如果nums*[*start*]* <= target && target < nums*[*mid*],目标值在前半段，使end=mid-1*

  • 否则，目标值在后半段，使start=mid+1*

否则，说明后半段是递增的

  • 如果nums[mid] < target && target <= nums[end],目标值在后半段，使start=mid+1

  • 否则，目标值在前半段，使end=mid-1

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
public int search(int[] nums, int target) {
        if (nums.length == 0)
            return -1;

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[mid] >= nums[left]) {
                // 说明数组在[0, mid]区间上是递增的
                if (nums[left] <= target && target < nums[mid])
                    // 说明target在[left, mid-1]区间内
                    right = mid - 1;
                else
                    // 说明target在[mid+1, right]区间内
                    left = mid + 1;
            } else {
                // 说明数组在[mid, right]区间上是递增的
                if (nums[mid] < target && target <= nums[right])
                    // 说明target在区间[mid+1, right]内
                    left = mid + 1;
                else
                    // 说明target在区间[left, mid-1]内
                    right = mid - 1;
            }
        }

        return -1;
    }

81: 搜索旋转排序数组 Ⅱ

题目描述

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

( 例如，数组 [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
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

题解

二分查找

因为存在重复的元素, 因此在33题中判断前后段升降时遇到了特殊情况. 在33题中是通过nums[mid] >= nums[left] 来判断前半段是否为增, 若存在重复元素, 则无法通过该方法判断例如 10111 的数组. 有两种判断方法:

  1. 出现这种情况时nums[left] 和nums[right] 一定是相等的.left++ 即可
  2. 将原来的判断条件分开来处理, 当nums[mid] > nums[left]时, 还按33题的方法去做, 添加一个nums[mid] = nums[left]的处理方法: 也是left++
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
public boolean search(int[] nums, int target) {
        if (nums.length == 0)
            return false;
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
                return true;

            if (nums[left] == nums[mid]) {
                left++;
                continue;
            }

            if (nums[left] < nums[mid]) {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[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

题解

二分查找

因为不存在重复的数字, 所以只需要考虑大于和等于的情况, 比较对象为nums[right]

  1. 循环二分： 设置 i,j 指针分别指向numbers 数组左右两端，m = (i + j) / 2 为每次二分的中点（ “/“ 代表向下取整除法），可分为以下三种情况：

    1. 当numbers[m] > numbers[j]时： m 一定在 左排序数组 中，即旋转点 x一定在[m + 1, j]闭区间内，因此执行i = m + 1；

    2. 当 numbers[m] < numbers[j]时： m 一定在 右排序数组 中，即旋转点 x 一定在[i, m] 闭区间内，因此执行j = m；

  2. 返回值： 当i = j时跳出二分循环，并返回 numbers[i]即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

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

题解

二分查找

这道题与153题有着高度的相似, 依然是将nums[mid]与nums[right]相比较, 不过是多考虑一个等于的情况, 采取的措施是right--.

如下图所示，寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 numbers[x] ，称 x 为 旋转点

  1. 循环二分： 设置 i,j 指针分别指向numbers 数组左右两端，m = (i + j) / 2 为每次二分的中点（ “/“ 代表向下取整除法），可分为以下三种情况：

    1. 当numbers[m] > numbers[j]时： m 一定在 左排序数组 中，即旋转点 x一定在[m + 1, j]闭区间内，因此执行i = m + 1；

    2. 当 numbers[m] < numbers[j]时： m 一定在 右排序数组 中，即旋转点 x 一定在[i, m] 闭区间内，因此执行j = m；

    3. 当 numbers[m] == numbers[j]时： 无法判断 m 在哪个排序数组中，即无法判断旋转点x 在 [i, m] 还是 [m + 1, j] 区间中。解决方案： 执行j = j - 1 缩小判断范围.

  2. 返回值： 当i = j时跳出二分循环，并返回 numbers[i]即可。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findMin(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
}

比较来看153题的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}
-------------本文结束感谢您的阅读-------------
可以请我喝杯奶茶吗