81. Search in Rotated Sorted Array II

Problem

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Constraints:

• 1 <= nums.length <= 5000
• -10⁴ <= nums[i] <= 10⁴
• nums is guaranteed to be rotated at some pivot.
• -10⁴ <= target <= 10⁴

Follow up: This problem is similar to 33. Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Test Cases

1
2

class Solution:
    def search(self, nums: List[int], target: int) -> bool:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, target, expected', [
    ([2,5,6,0,0,1,2], 0, True),
    ([2,5,6,0,0,1,2], 3, False),

    ([1,0,1,1,1], 0, True),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, target, expected):
    assert sol.search(nums, target) == expected

Thoughts

33. Search in Rotated Sorted Array 的进阶版，nums 中可能存在重复元素。

直接把 problem 33 的代码搬过来（修改返回值为 bool）是不行的，有些 case 会失败。比如 nums = [1,0,1,1,1]、target = 0，那么初始时 l = 0、r = 4、m = 2，那么 nums[l] == nums[m] == nums[r] == 1 ≠ 0，无法确定数组的最小值（或最大值）在哪半边。一个简单的办法是同时收缩一点点两个边界，即令 l = l + 1、r = r - 1。

最坏情况下，每次都只能收缩一点点左右边界，时间复杂度 O(n)；但平均情况下时间复杂度 O(log n)。空间复杂度 O(1)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) >> 1
            if nums[m] == target:
                return True
            elif nums[l] == nums[m] == nums[r]:
                l += 1
                r -= 1
            elif (nums[l] <= target < nums[m]) or (nums[l] > nums[m] and (nums[l] <= target or target < nums[m])):
                r = m - 1
            else:
                l = m + 1

        return False

参考资料

• 本文引用

  • 33. Search in Rotated Sorted Array

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章