尧图网页设计 
LeetCode-Go 题解81. Search in Rotated Sorted Array II 含重复元素的旋转数组搜索【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇基于 LeetCode-Go 仓库中 0081.Search-in-Rotated-Sorted-Array-II 的官方题解文档展开深入讲解如何在升序数组 未知旋转点 允许重复元素三者叠加的数组中用二分思想判断目标值是否存在。读完本文你将掌握重复元素如何破坏传统二分旋转数组的判定条件、为什么最坏时间复杂度会退化到 O(n)以及本仓库 Go 实现中双指针收窄 三路分支的完整细节与对应测试用例并可顺带对照 33. Search in Rotated Sorted Array 理解两者的差异。题目描述假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如数组[0,0,1,2,2,5,6]可能变为[2,5,6,0,0,1,2]。给定一个目标值target编写一个函数判断该目标值是否存在于数组中。若存在返回true否则返回false。示例 1Input: nums [2,5,6,0,0,1,2], target 0 Output: true示例 2Input: nums [2,5,6,0,0,1,2], target 3 Output: false进阶问题Follow up本题是 Search in Rotated Sorted Array 的延伸题目区别在于本题的nums可能包含重复元素这会影响到程序的时间复杂度吗会有怎样的影响为什么题目大意本题是第 33 题的加强版数组原本从小到大排列且其中存在重复数字但数组在某个随机位置被旋转形成前段大、后段小两段各自有序的子序列。要求在这样的数组中查找目标值找到输出true找不到输出false。原文档明确指出本题实现代码与第 33 题完全一样只是输出从索引变成了布尔值具体思路可参见第 33 题。解题思路1. 整体框架仍然是二分查找旋转数组由两段单调递增的子序列拼接而成虽然存在一个断开点但整体仍然基本有序因此可以使用二分查找思想。核心是每次取中点mid后根据nums[mid]与区间端点的大小关系判断mid落在哪一段有序区间内从而确定向哪一侧继续收缩。对于不含重复元素的第 33 题可以通过nums[mid]与nums[low]或nums[high]的比较唯一确定哪半边有序但当数组中允许出现重复元素后会出现nums[low] nums[mid] nums[high]这类无法判断方向的情况此时必须特殊处理这正是本题与第 33 题的本质差异。2. 重复元素带来的退化最坏 O(n)原文档的进阶问题重复元素会影响时间复杂度吗的答案是会。当nums[low] nums[mid] nums[high]时无法通过比较判断旋转点在左侧还是右侧唯一的办法是把两端与nums[mid]相等的元素逐个收窄排除。在最坏情况下例如数组中全部元素相等、目标值不存在时二分退化成了线性扫描时间复杂度从 O(log n) 退化为O(n)。例如输入[1,1,1,1,1,1,1]查找2每一步都只能把low和high各移动一位最终遍历完整个数组。3. 仓库源码逐步拆解本仓库的 Go 实现在 81. Search in Rotated Sorted Array II.go核心函数如下func search(nums []int, target int) bool { if len(nums) 0 { return false } low, high : 0, len(nums)-1 for low high { mid : low (high-low)1 if nums[mid] target { return true } else if nums[mid] nums[low] { // 在数值大的一部分区间里 if nums[low] target target nums[mid] { high mid - 1 } else { low mid 1 } } else if nums[mid] nums[high] { // 在数值小的一部分区间里 if nums[mid] target target nums[high] { low mid 1 } else { high mid - 1 } } else { if nums[low] nums[mid] { low } if nums[high] nums[mid] { high-- } } } return false }代码整体是一个low high的二分循环mid : low (high-low)1使用移位替代除法计算中点避免(lowhigh)的整数溢出。循环体分四条分支命中目标nums[mid] target直接返回true落在数值较大区间nums[mid] nums[low]说明[low, mid]这一段是严格递增的左段大值段。若target落在[nums[low], nums[mid])左闭右开区间内说明目标在左半段收缩high mid - 1否则收缩low mid 1落在数值较小区间nums[mid] nums[high]说明[mid, high]这一段是严格递增的右段小值段。若target落在(nums[mid], nums[high]]左开右闭区间内收缩low mid 1否则收缩high mid - 1端点相等、方向不明既不满足nums[mid] nums[low]也不满足nums[mid] nums[high]即nums[low]、nums[mid]、nums[high]存在相等的情况无法判定哪半边有序。此时采用逐步收窄策略nums[low] nums[mid]则lownums[high] nums[mid]则high--把与中点值相同的端点元素一个个排除直到区间重新具备可判定性。对照 33. Search in Rotated Sorted Array.go 中的search33可以看到两者的分支结构与比较逻辑完全一致唯一区别是第 33 题命中时return mid、未命中return -1而本题命中return true、未命中return false。这印证了原文档实现代码完全一样只不过输出变了的表述。4. 边界条件与空数组函数开头对空数组做了防御if len(nums) 0 { return false }。对应测试用例para81{[]int{}, 1}与期望false见下方测试分析说明空数组中任何目标值都不存在。测试用例与验证本仓库的测试文件 81. Search in Rotated Sorted Array II_test.go 采用参数 期望答案的结构化表驱动测试para81保存输入nums与targetans81保存期望的布尔输出覆盖了 9 组典型场景输入 numstarget期望覆盖意图[2,5,6,0,0,1,2]0true题目官方示例旋转点两侧均有重复[2,5,6,0,0,1,2]3false题目官方示例目标不存在[]1false空数组边界[1,0,1,1,1]0truenums[low] nums[mid]且nums[mid] nums[high]需靠low/high--收窄才能找到目标[1,1,1,0,1]0true对称场景旋转点偏向右侧同样考验退化分支[4,5,6,7,0,1,2]6true无重复元素的经典旋转数组第 33 题场景[4,5,6,7,0,1,2]0true命中旋转点后的小值段[4,5,6,7,0,1,2]3false目标介于两段之间不存在[6,7,0,1,2]2true较短数组旋转点在首元素处其中[1,0,1,1,1]与[1,1,1,0,1]两组用例正是针对重复元素导致方向不可判定这一难点设计的若沿用第 33 题不带收窄分支的实现这两组会因nums[low] nums[mid]而错误收缩区间。测试通过t.Fatalf在结果不符时中断并打印【input】:%v 【output】:%v便于定位。仓库根目录的 gotest.sh 提供了统一的测试与覆盖率入口go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...可一键运行leetcode目录下所有题目的测试并生成覆盖率文件也适用于单独验证本题例如执行go test -v -run Test_Problem81 ./leetcode/0081.Search-in-Rotated-Sorted-Array-II/。复杂度分析平均/常见情况只要不触发三端点相等的退化分支每轮迭代将搜索区间缩小一半时间复杂度为 O(log n)最坏情况当输入大量重复元素典型如nums全为同一值且目标不存在时退化分支每次只移动low或high一位最坏时间复杂度为O(n)空间复杂度全程仅使用low、high、mid三个常量级变量为 O(1)。小结81 题是 33 题的去重约束变体两者的二分框架一致差别仅在重复元素破坏方向判定后必须通过端点与中点相等则逐步收窄的分支兜底。从本仓库实现与测试可以看出判定区间有序性的两个条件nums[mid] nums[low]与nums[mid] nums[high]均采用严格不等这正是为了避免把相等情形误判为有序段而一旦落入 else 分支就用双指针收窄消去冗余重复值换取后续区间的可判定性。理解这一以 O(n) 最坏情况换取正确性的取舍是掌握本题的关键也是回答其进阶问题的核心论据。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：81. Search in Rotated Sorted Array II 含重复元素的旋转数组搜索
LeetCode-Go 题解81. Search in Rotated Sorted Array II 含重复元素的旋转数组搜索【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇基于 LeetCode-Go 仓库中 0081.Search-in-Rotated-Sorted-Array-II 的官方题解文档展开深入讲解如何在升序数组 未知旋转点 允许重复元素三者叠加的数组中用二分思想判断目标值是否存在。读完本文你将掌握重复元素如何破坏传统二分旋转数组的判定条件、为什么最坏时间复杂度会退化到 O(n)以及本仓库 Go 实现中双指针收窄 三路分支的完整细节与对应测试用例并可顺带对照 33. Search in Rotated Sorted Array 理解两者的差异。题目描述假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如数组[0,0,1,2,2,5,6]可能变为[2,5,6,0,0,1,2]。给定一个目标值target编写一个函数判断该目标值是否存在于数组中。若存在返回true否则返回false。示例 1Input: nums [2,5,6,0,0,1,2], target 0 Output: true示例 2Input: nums [2,5,6,0,0,1,2], target 3 Output: false进阶问题Follow up本题是 Search in Rotated Sorted Array 的延伸题目区别在于本题的nums可能包含重复元素这会影响到程序的时间复杂度吗会有怎样的影响为什么题目大意本题是第 33 题的加强版数组原本从小到大排列且其中存在重复数字但数组在某个随机位置被旋转形成前段大、后段小两段各自有序的子序列。要求在这样的数组中查找目标值找到输出true找不到输出false。原文档明确指出本题实现代码与第 33 题完全一样只是输出从索引变成了布尔值具体思路可参见第 33 题。解题思路1. 整体框架仍然是二分查找旋转数组由两段单调递增的子序列拼接而成虽然存在一个断开点但整体仍然基本有序因此可以使用二分查找思想。核心是每次取中点mid后根据nums[mid]与区间端点的大小关系判断mid落在哪一段有序区间内从而确定向哪一侧继续收缩。对于不含重复元素的第 33 题可以通过nums[mid]与nums[low]或nums[high]的比较唯一确定哪半边有序但当数组中允许出现重复元素后会出现nums[low] nums[mid] nums[high]这类无法判断方向的情况此时必须特殊处理这正是本题与第 33 题的本质差异。2. 重复元素带来的退化最坏 O(n)原文档的进阶问题重复元素会影响时间复杂度吗的答案是会。当nums[low] nums[mid] nums[high]时无法通过比较判断旋转点在左侧还是右侧唯一的办法是把两端与nums[mid]相等的元素逐个收窄排除。在最坏情况下例如数组中全部元素相等、目标值不存在时二分退化成了线性扫描时间复杂度从 O(log n) 退化为O(n)。例如输入[1,1,1,1,1,1,1]查找2每一步都只能把low和high各移动一位最终遍历完整个数组。3. 仓库源码逐步拆解本仓库的 Go 实现在 81. Search in Rotated Sorted Array II.go核心函数如下func search(nums []int, target int) bool { if len(nums) 0 { return false } low, high : 0, len(nums)-1 for low high { mid : low (high-low)1 if nums[mid] target { return true } else if nums[mid] nums[low] { // 在数值大的一部分区间里 if nums[low] target target nums[mid] { high mid - 1 } else { low mid 1 } } else if nums[mid] nums[high] { // 在数值小的一部分区间里 if nums[mid] target target nums[high] { low mid 1 } else { high mid - 1 } } else { if nums[low] nums[mid] { low } if nums[high] nums[mid] { high-- } } } return false }代码整体是一个low high的二分循环mid : low (high-low)1使用移位替代除法计算中点避免(lowhigh)的整数溢出。循环体分四条分支命中目标nums[mid] target直接返回true落在数值较大区间nums[mid] nums[low]说明[low, mid]这一段是严格递增的左段大值段。若target落在[nums[low], nums[mid])左闭右开区间内说明目标在左半段收缩high mid - 1否则收缩low mid 1落在数值较小区间nums[mid] nums[high]说明[mid, high]这一段是严格递增的右段小值段。若target落在(nums[mid], nums[high]]左开右闭区间内收缩low mid 1否则收缩high mid - 1端点相等、方向不明既不满足nums[mid] nums[low]也不满足nums[mid] nums[high]即nums[low]、nums[mid]、nums[high]存在相等的情况无法判定哪半边有序。此时采用逐步收窄策略nums[low] nums[mid]则lownums[high] nums[mid]则high--把与中点值相同的端点元素一个个排除直到区间重新具备可判定性。对照 33. Search in Rotated Sorted Array.go 中的search33可以看到两者的分支结构与比较逻辑完全一致唯一区别是第 33 题命中时return mid、未命中return -1而本题命中return true、未命中return false。这印证了原文档实现代码完全一样只不过输出变了的表述。4. 边界条件与空数组函数开头对空数组做了防御if len(nums) 0 { return false }。对应测试用例para81{[]int{}, 1}与期望false见下方测试分析说明空数组中任何目标值都不存在。测试用例与验证本仓库的测试文件 81. Search in Rotated Sorted Array II_test.go 采用参数 期望答案的结构化表驱动测试para81保存输入nums与targetans81保存期望的布尔输出覆盖了 9 组典型场景输入 numstarget期望覆盖意图[2,5,6,0,0,1,2]0true题目官方示例旋转点两侧均有重复[2,5,6,0,0,1,2]3false题目官方示例目标不存在[]1false空数组边界[1,0,1,1,1]0truenums[low] nums[mid]且nums[mid] nums[high]需靠low/high--收窄才能找到目标[1,1,1,0,1]0true对称场景旋转点偏向右侧同样考验退化分支[4,5,6,7,0,1,2]6true无重复元素的经典旋转数组第 33 题场景[4,5,6,7,0,1,2]0true命中旋转点后的小值段[4,5,6,7,0,1,2]3false目标介于两段之间不存在[6,7,0,1,2]2true较短数组旋转点在首元素处其中[1,0,1,1,1]与[1,1,1,0,1]两组用例正是针对重复元素导致方向不可判定这一难点设计的若沿用第 33 题不带收窄分支的实现这两组会因nums[low] nums[mid]而错误收缩区间。测试通过t.Fatalf在结果不符时中断并打印【input】:%v 【output】:%v便于定位。仓库根目录的 gotest.sh 提供了统一的测试与覆盖率入口go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...可一键运行leetcode目录下所有题目的测试并生成覆盖率文件也适用于单独验证本题例如执行go test -v -run Test_Problem81 ./leetcode/0081.Search-in-Rotated-Sorted-Array-II/。复杂度分析平均/常见情况只要不触发三端点相等的退化分支每轮迭代将搜索区间缩小一半时间复杂度为 O(log n)最坏情况当输入大量重复元素典型如nums全为同一值且目标不存在时退化分支每次只移动low或high一位最坏时间复杂度为O(n)空间复杂度全程仅使用low、high、mid三个常量级变量为 O(1)。小结81 题是 33 题的去重约束变体两者的二分框架一致差别仅在重复元素破坏方向判定后必须通过端点与中点相等则逐步收窄的分支兜底。从本仓库实现与测试可以看出判定区间有序性的两个条件nums[mid] nums[low]与nums[mid] nums[high]均采用严格不等这正是为了避免把相等情形误判为有序段而一旦落入 else 分支就用双指针收窄消去冗余重复值换取后续区间的可判定性。理解这一以 O(n) 最坏情况换取正确性的取舍是掌握本题的关键也是回答其进阶问题的核心论据。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考