寻找旋转排序数组中的最小值 II 题目描述 已知一个长度为 n 的数组，预先按照升序排列，但我们在某个未知的下标 k (0 <= k < n) 上进行了旋转，使得数组变为 [ nums[ k], nums[ k+1], ..., nums[ n-1], nums[ 0], nums[ 1], ..., nums[ k-1]]。例如，数组 [ 0,1,4,4,5,6,7] 可能变为 [ 4,5,6,7,0,1,4 ]。重要的是，数组中可能包含重复的元素。 请你找出并返回数组中的最小元素。 解题过程 问题分析与核心挑战 这道题是经典问题“寻找旋转排序数组中的最小值”的进阶版本。关键区别在于数组中可能包含 重复元素 。这引入了一个新的挑战：当二分查找的中间元素与边界元素相等时，我们无法立即判断最小值位于哪一半区间。 基础思路：二分查找的变体 即使数组被旋转，它仍然在某种程度上保持着有序性。我们可以使用二分查找的思想，但需要针对重复元素的情况调整策略。我们定义两个指针： left 指向当前搜索区间的左端， right 指向右端。 详细步骤分解 步骤 1：初始化 设置 left = 0 ， right = nums.length - 1 。 步骤 2：循环条件 当 left < right 时，进入循环。我们的目标是将搜索区间缩小到只包含一个元素，那个元素就是最小值。 步骤 3：计算中间点 计算中间下标 mid = left + (right - left) // 2 。使用这种写法是为了防止 (left + right) 可能出现的整数溢出。 步骤 4：比较 nums[mid] 和 nums[right] （关键步骤） 这是算法的核心。我们不比较 mid 和 left ，而是比较 mid 和 right 。这是因为当数组包含重复元素时，比较 mid 和 left 的情况会更复杂。比较 mid 和 right 的逻辑更清晰： 情况 A： nums[mid] > nums[right] 这表示中间点位于旋转点左侧较大的递增序列中，而最小值肯定位于 mid 的 右侧 （因为右侧是包含最小值的、较小的递增序列）。 因此，我们可以安全地将搜索范围缩小到右半部分： left = mid + 1 。 例子 ： [3, 4, 5, 1, 2] ，若 mid 是 5（下标2）， right 是 2（下标4）， 5 > 2 ，最小值1在 mid 右边。 情况 B： nums[mid] < nums[right] 这表示中间点位于旋转点右侧较小的递增序列中（或者整个数组根本没有旋转）。那么，最小值一定位于 mid 的 左侧 （包括 mid 本身），因为从 mid 到 right 是递增的， mid 已经是最小值或比最小值大）。 因此，我们将搜索范围缩小到左半部分（包括 mid ）： right = mid 。 例子 ： [5, 1, 2, 3, 4] ，若 mid 是 2（下标2）， right 是 4（下标4）， 2 < 4 ，最小值1在 mid 左边。 情况 C： nums[mid] == nums[right] （处理重复元素的关键） 这是最棘手的情况。由于存在重复元素，我们无法判断最小值在左半边还是右半边。例如： [1, 0, 1, 1, 1] （最小值0在左侧） [1, 1, 1, 0, 1] （最小值0在右侧） 在这种情况下，我们无法通过一次比较决定舍弃哪一半。但是，我们可以确定一件事：既然 nums[mid] 等于 nums[right] ，那么无论 right 是不是最小值，我们都有一个“备份”在 mid 的位置（或者更左边）。因此，我们可以安全地将右边界 right 向左移动一位（ right = right - 1 ），来缩小搜索范围，同时不会丢失最小值。 原理 ：如果 nums[right] 是唯一的最小值，那么 nums[mid] 也等于这个值，所以最小值仍然在 [left, right] 区间内。如果 nums[right] 不是唯一的最小值，那么移动它更没问题。 步骤 5：循环结束与返回结果 当循环条件 left < right 不满足时，即 left 等于 right ，此时它们指向同一个元素。这个元素就是整个数组中的最小值。返回 nums[left] （或 nums[right] ）。 算法示例 让我们用题目中的例子 nums = [4, 5, 6, 7, 0, 1, 4] 来走一遍流程。 初始： left = 0 , right = 6 。 nums[left]=4 , nums[right]=4 。 迭代 1 : mid = 0 + (6-0)//2 = 3 。 nums[3] = 7 ， nums[6] = 4 。 7 > 4 ，属于 情况A 。 left = mid + 1 = 4 。 现在区间是 [0, 1, 4] （下标4到6）。 迭代 2 : left=4, right=6 。 mid = 4 + (6-4)//2 = 5 。 nums[5] = 1 ， nums[6] = 4 。 1 < 4 ，属于 情况B 。 right = mid = 5 。 现在区间是 [0, 1] （下标4到5）。 迭代 3 : left=4, right=5 。 mid = 4 + (5-4)//2 = 4 。 nums[4] = 0 ， nums[5] = 1 。 0 < 1 ，属于 情况B 。 right = mid = 4 。 现在 left=4 等于 right=4 ，循环结束。返回 nums[4] = 0 。 总结 这个算法是二分查找的一个巧妙变体。通过比较中间元素与右边界元素，可以有效地处理旋转。当遇到相等元素时，通过逐步收缩右边界来保证算法的正确性。其时间复杂度在最坏情况下（所有元素都相同）会退化为 O(n)，但在平均情况下仍然是 O(log n)。