LeetCode 81. 搜索旋转排序数组 II（中）

LeetCode 33. 搜索旋转排序数组 的改进。
出现了重复数字，需要在二分查找的预处理阶段进行一些特殊判断。

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
进阶:
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
影响：由于要去重，时间复杂度从 \(O(log N)\) 变成了 \(O(log N + N)\)。

示例

示例 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

考察知识点

二分查找、数组

核心思想

方法一、预处理加二分查找
预处理：由于 nums 存在重复数字，然后又进行了旋转。所以预处理阶段，要找到旋转点，根据旋转点找到可能存在 target 且有序的那一部分 sub_list。
二分查找：在 sub_list 利用二分查找寻找 target。

方法二、直接二分查找
这道是之前那道 Search in Rotated Sorted Array 的延伸，现在数组中允许出现重复数字，这个也会影响我们选择哪半边继续搜索，由于之前那道题不存在相同值，我们在比较中间值和最右值时就完全符合之前所说的规律：
如果中间的数小于最右边的数，则右半段是有序的，。
若中间数大于最右边数，则左半段是有序的。
而如果可以有重复值，就会出现来面两种情况，[3 1 1] 和 [1 1 3 1]，对于这两种情况，中间值等于最右值时，目标值3既可以在左边又可以在右边，那怎么办么，对于这种情况其实处理非常简单，只要把最右值向左一位即可继续循环，如果还相同则继续移，直到移到不同值为止，然后其他部分还采用 Search in Rotated Sorted Array 中的方法。

Python版本

  • 方法一的实现
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
43
44
45
46
47
from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        # step1、特判
        if not len(nums) or (len(nums) == 1 and nums[0] != target):  return False
        if len(nums) == 1 and nums[0] == target:  return True
        _min = min(nums)
        
        # step2、确定sub_list，其中可能存在 target，且sub_list有序，可以用于二分查找。
        if _min == target:
            return True
        min_index = nums.index(_min)
        if min_index == 0:
            if nums[-1] > nums[0]:  # [1, 3]的情况，直接跳过，认为当前nums就是sub_list了。
                pass
            else:  # [1, 3, 1, 1]的情况
                while len(nums) >=2 and nums[-1] == nums[0]:  # 这里要注意,可能出现最终len(nums)为0的情况，所以要做个判断。
                    nums = nums[:-1]
        elif min_index != 0 and target >= nums[0]:
            nums = nums[:min_index]   # 在前面一个区间做二分查找
        else:
            nums = nums[min_index:]  # 在后面一个区间做二分查找
        
        # step3、得到sub_list，这个sub_list包含target且一定有序，在sub_list中进行二分查找。
        left = 0
        right = len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if target == nums[mid]:
                return True
            elif target < nums[mid]:  # 在左区间 right左移
                right = mid
            else:  # 在右区间 left右移 target >= nums[mid + 1]
                left = mid + 1
        return False

Input = [[3,1,1], [1,3], [1], [1,1], [1], [1,3,1,1], [1,3], [2,5,6,0,0,1,2], [2,5,6,0,0,1,2]]
Input1 = [3, 1, 1, 0, 0, 3, 3, 0, 3]
Answer = [True, True, True, False, False, True, True, True, False]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
        print("-"*50)
        reslut = solution.search(Input[i], Input1[i])
        print(reslut == Answer[i])

时间复杂度：\(O(nlogn + n)\)，二分查找的时间复杂度是 \(O(nlogn)\)，而 nums = nums[:-1] 最坏情况下可能执行 n 次，所以最终的时间复杂度为 \(O(nlogn + n)\)。
空间复杂度：\(O(1)\)，只是用了常数级别的额外空间。
执行用时 :44 ms, 在所有 Python3 提交中击败了80.02%的用户
内存消耗 :13.7 MB, 在所有 Python3 提交中击败了5.37%的用户

  • 方法二的实现
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
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        # step1、特判
        if not len(nums) or (len(nums) == 1 and nums[0] != target):  return False
        if len(nums) == 1 and nums[0] == target:  return True
        _min = min(nums)

        # 由于出现了重复数字，所以不能再通过找到list中的最小元素来分割nums为左边值或者右边值。比如[1, 3, 1, 1]的出现，由于最小值1就在第0位，就分割不了了。
        # 所以用中间值分隔
        n = len(nums)
        left,right = 1, n - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:  return True
            if nums[mid] < nums[right]:  # 如果中间的数小于最右边的数，则右半段是有序的。
                # 以下就是关键代码
                # 先在右半段（有序）的里面用二分查找找target，同时根据nums[mid]、nums[right]和target的值的关系，更新left和right。
                if nums[mid] < target and nums[right] >= target:  left = mid + 1
                else:  right = mid -1
            elif nums[mid] > nums[right]:  # 若中间数大于最右边数，则左半段是有序的
                # 以下就是关键代码
                # 先在左半段（有序）的里面用二分查找找target，同时根据nums[mid]、nums[left]和target的值的关系，更新left和right。
                if nums[left] <= target and nums[mid] > target:  right = mid - 1
                else: left = mid + 1
            else:  right -= 1  # 这里的right -= 1就类似方法一中的 nums = nums[:-1]
        return False

258 / 275 个通过测试用例

参考连接

Grandyang