0081. Search in Rotated Sorted Array II ======================================= 题目信息 -------- :题号: 0081. 搜索旋转排序数组 II :难度: Medium :主题: 数组、二分查找、旋转有序数组、重复值 :原题: `LeetCode 0081 `_ :重点: 从线性扫描,推导到重复端点消歧,再恢复有序半区二分 题目重述 -------- 给定一个非递减数组。它在某个未知下标处旋转后形成数组 ``nums``,其中允许出现重复值。 判断整数 ``target`` 是否存在于 ``nums`` 中。 旋转表示把原数组分成前后两段,再交换两段顺序。例如: .. code-block:: text 原数组:[0,1,2,4,4,5,6] 旋转后:[4,5,6,0,1,2,4] 约束如下: - ``1 <= nums.length <= 5000`` - ``-10^4 <= nums[i], target <= 10^4`` 自建示例 -------- .. code-block:: text 输入:nums = [4,4,5,6,0,1,2,4], target = 1 输出:true 目标位于旋转点右侧的有序段中。 .. code-block:: text 输入:nums = [1,1,1,0,1], target = 0 输出:true 初始左端、中点和右端都等于 1,必须先移除没有顺序信息的重复端点。 .. code-block:: text 输入:nums = [2,2,2,2,2], target = 3 输出:false 所有元素相同且都不是目标,二分查找会逐步退化为线性消歧。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: bool linearScan(const std::vector& nums, int target) { for (int value : nums) { if (value == target) { return true; } } return false; } bool discardOneDuplicateEnd(const std::vector& nums, int target) { int left = 0; int right = static_cast(nums.size()) - 1; while (left <= right) { int middle = left + (right - left) / 2; if (nums[middle] == target) { return true; } if (nums[left] == nums[middle]) { ++left; continue; } if (nums[left] < nums[middle]) { if (nums[left] <= target && target < nums[middle]) { right = middle - 1; } else { left = middle + 1; } } else { if (nums[middle] < target && target <= nums[right]) { left = middle + 1; } else { right = middle - 1; } } } return false; } bool discardBothDuplicateEnds(const std::vector& nums, int target) { int left = 0; int right = static_cast(nums.size()) - 1; while (left <= right) { int middle = left + (right - left) / 2; if (nums[middle] == target) { return true; } if (nums[left] == nums[middle] && nums[middle] == nums[right]) { ++left; --right; continue; } if (nums[left] <= nums[middle]) { if (nums[left] <= target && target < nums[middle]) { right = middle - 1; } else { left = middle + 1; } } else { if (nums[middle] < target && target <= nums[right]) { left = middle + 1; } else { right = middle - 1; } } } return false; } public: bool search(std::vector& nums, int target) { return discardBothDuplicateEnds(nums, target); } }; 题解 ---- 线性扫描起点 ~~~~~~~~~~~~ 直接检查每个元素一定正确,时间为 ``O(n)``。要继续优化,必须利用旋转数组仍由两个非递减段组成这一结构。 没有重复值时,中点至少有一侧可以根据端点关系确定为有序段。若目标落在该段的值域内,就保留该段; 否则删除它。这样每轮可以排除约一半候选。 重复值造成歧义 ~~~~~~~~~~~~~~ 数组 ``[1,0,1,1,1]`` 的初始状态为: .. code-block:: text left = 0, middle = 2, right = 4 nums[left] = nums[middle] = nums[right] = 1 仅凭三个值无法判断旋转点在中点左侧还是右侧,因此也无法证明哪一半有序。 这不是二分模板的边界错误,而是重复值确实抹去了顺序信息。 单侧消歧 ~~~~~~~~ 中点已经确认不等于目标。若 ``nums[left] == nums[middle]``,左端点也不等于目标,删除左端点是安全的: .. code-block:: text ++left 持续删除后,要么找到目标,要么出现 ``nums[left] != nums[middle]``,此时可以重新识别有序半区。 这种写法只需要一个消歧分支,最坏仍可能逐个删除元素。 双侧消歧 ~~~~~~~~ 当三端值全部相等时,中点不是目标意味着左右端点也都不是目标,因此可以同时执行: .. code-block:: text ++left --right 这比只删除左端点对全相等区间更直接。若只有一侧与中点相等,则仍可能通过另一侧的大小关系识别有序半区, 不能无条件同时删除两端。 有序半区 ~~~~~~~~ 完成必要的消歧后,分两种情况。 ``nums[left] <= nums[middle]`` 表示左半区非递减。目标满足下面的半开值域时,只可能位于左半区: .. code-block:: text nums[left] <= target < nums[middle] 否则搜索右半区。 若 ``nums[left] > nums[middle]``,旋转点位于左半区,右半区必然非递减。目标满足下面的值域时保留右半区: .. code-block:: text nums[middle] < target <= nums[right] 左右条件采用不同的开闭边界,是因为中点已经检查过,不能再次保留在新区间中。 循环不变量 ~~~~~~~~~~ 每轮开始时,若目标存在,则它一定仍位于闭区间 ``[left, right]`` 中。 - 命中中点时立即返回。 - 消歧只删除已知不等于目标的端点。 - 有序半区判断只删除值域不可能包含目标的一半。 因此算法不会遗漏目标。区间耗尽时,所有可能位置均已排除。 退化原因 ~~~~~~~~ 在 ``[2,2,2,2,2]`` 中查找 3 时,每轮都只能删除重复端点,无法按比例缩小区间。 所以该算法在歧义很少时具有二分查找的 ``O(log n)`` 行为,最坏时间为 ``O(n)``。 重复值造成的信息缺失决定了这种最坏退化;常量空间算法无法保证每轮都排除一半元素。 复杂度 ~~~~~~ 线性扫描时间为 ``O(n)``。两种消歧二分在无大量歧义时为 ``O(log n)``,最坏为 ``O(n)``; 它们都只维护几个下标,额外空间为 ``O(1)``。