【4.7】LeetCode每日一题· 搜索旋转排序数组 II

2021年04月07日 12时29分

标签： LeetCode 二分

## 题目描述
已知存在一个按非降序排列的整数数组`nums`，数组中的值不必互不相同。

在传递给函数之前，`nums`在预先未知的某个下标`k（0 <= k < nums.length）`上进行了**旋转**，使数组变为`[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`（下标 从**0开始**计数）。例如， `[0,1,2,4,4,4,5,6,6,7]`在下标`5`处经旋转后可能变为`[4,5,6,6,7,0,1,2,4,4]`。

给你**旋转后**的数组`nums`和一个整数`target`，请你编写一个函数来判断给定的目标值是否存在于数组中。如果`nums`中存在这个目标值`target`，则返回`true`，否则返回`false`。

#### 示例1
```
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
```

#### 示例2
```
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
```

#### 提示
```
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
```

#### 进阶
* 这是[搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/description/)的延伸题目，本题中的`nums`可能包含重复元素。
* 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii "题目链接")

## 解题思路
先看前置题目[搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/description/)

### 前置问题题目描述
整数数组`nums`按升序排列，数组中的值**互不相同**。

在传递给函数之前，`nums`在预先未知的某个下标`k（0 <= k < nums.length）`上进行了**旋转**，使数组变为`[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`（下标**从 0 开始**计数）。例如，` [0,1,2,4,5,6,7]`在下标 3 处经旋转后可能变为`[4,5,6,7,0,1,2]`。

给你**旋转后**的数组`nums`和一个整数`target`，如果`nums`中存在这个目标值`target`，则返回它的下标，否则返回`-1`。

##### 示例1
```
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
```

##### 示例2
```
输入：nums = [1], target = 0
输出：-1
```

##### 提示
```
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
```

##### 进阶
你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

对于一个已排序的数组，可以使用**二分查找**在$$O(log n)$$的时间复杂度内判断某一个数是否存在该数组中，并找出它的下标。

但本题中的数组并非完全有序，而是部分有序。这样还可以进行二分查找吗？实际上也是可以的。

因为数组是有序数组经过**旋转**之后得到的，因此我们有如下两个结论：
1. 如果有`nums[i] < nums[j] (i < j)`，那么`nums[i..j]`有序。另外一部分可能有序，也可能无序。
2. 把原数组分成任意两个子数组，必定有一个子数组是有序的。

有了这两个结论，对于二分查找中，分成的左右两个子数组：
* 可以首先判断哪一个子数组是有序的。对于有序子数组`nums[i..j]`，其中元素的值必定在子数组第一个元素值到最后一个元素值的范围内，即`nums[i] <= nums[k] <= nums[j], i <= k <= j`，因此如果要查询的元素`target`在此范围内，则下一步在这一有序子数组中继续进行二分；
* 否则，可以断定`target`如果存在，则一定在另一个子数组中，就在另一个子数组范围内二分。

综上，可以得出代码。

#### 前置问题代码
```cpp
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1, mid;
        while(l < r){
            mid = ((r-l)>>1)+l;
            // 左边满足升序
            if(nums[l] < nums[mid]){
                // 要找的值在左侧
                if(target >= nums[l] && target <= nums[mid]){
                    r = mid;
                }else{
                    l = mid + 1;
                }
            }
            // 右边满足升序
            else{
                // 要找的值在右侧
                if(target >= nums[mid+1] && target <= nums[r]){
                    l = mid + 1;
                }else{
                    r = mid;
                }
            }
        }
        return nums[l] == target? l: -1;
    }
};
```

#### 前置问题用时和内存
> 执行用时：0 ms，在所有 C++提交中击败了100.00 %的用户
> 内存消耗：10.7 MB，在所有 C++提交中击败了93.36 %的用户**

那么对于本题，数组中的元素不再是不重复的，这导致了在二分的时候，我们**无法判断应该在哪个子数组中进行下一次二分**。例如对于：`[3, 1, 3, 3, 3], target = 1`，首次二分时两个子数组分别为`[3, 1, 3], [3, 3]`，此时无法根据`nums[l] = 3, nums[mid] = 3, nums[mid+1] = 3 以及 nums[r] = 3`判断，到底哪个子数组才是有序的，进而也就无法判断到底应该在哪一个区间进行继续二分。

在此时，我们只能进一步对`l`指针向后遍历，判断左子数组是否为有序的；如果判断出左子数组并非有序，此时还要根据新的`l`指针算出`mid`，然后确定应该在哪一个子数组中进行下一步二分。

因为需要对`l`和`r`进行遍历，因此最坏情况下时间复杂度是$$O(n)$$。

## 代码
```cpp
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1, mid;
        while(l < r){
            mid = ((r-l)>>1)+l;
            while(l < mid && nums[l] == nums[mid]) l++;
            if(nums[l] < nums[mid]){
                // 要找的值在左侧
                if(target >= nums[l] && target <= nums[mid]){
                    r = mid;
                }else{
                    l = mid + 1;
                }
            }
            else{
                mid = ((r-l)>>1)+l;
                while(r > mid && nums[r] == nums[mid]) r--;
                // 要找的值在右侧
                if(target >= nums[mid+1] && target <= nums[r]){
                    l = mid + 1;
                }else{
                    r = mid;
                }
            }
        }
        return nums[l] == target;
    }
};
```

## 用时和内存
> 执行用时：8 ms，在所有 C++提交中击败了60.01 %的用户
> 内存消耗：13.6 MB，在所有 C++提交中击败了54.25 %的用户**

附上直接遍历的用时和内存。
P.S.: 不如直接遍历(x)

## 直接遍历用时和内存
> 执行用时：0 ms，在所有 C++提交中击败了100.00 %的用户
> 内存消耗：13.5 MB，在所有 C++提交中击败了82.58%的用户**

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.7】LeetCode每日一题· 搜索旋转排序数组 II

所有评论

暂无评论

新增评论