题解 | #旋转数组的最小数字#
旋转数组的最小数字
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
def minNumberInRotateArray(self , nums: List[int]) -> int:
# write code here
left, right = 0, len(nums)-1
while left < right:
mid = (right + left) // 2
if nums[mid] == nums[right]:
right -= 1
elif nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]
在这个问题中，我们是在寻找旋转数组的最小值。当我们查看旋转数组时，会注意到，如果数组被旋转了，那么最小值一定位于旋转的位置，也就是说，在旋转点的左侧，所有的元素都会大于旋转点的右侧的元素。因此，我们可以通过比较中间元素与数组的右端元素来确定最小值是在中间元素的左侧还是右侧。
这里的比较逻辑是：
- 如果
nums[mid] > nums[right]，这意味着中间元素位于旋转点的左侧，最小值应该位于中间元素的右侧，所以我们可以将左边界移动到mid + 1。 - 如果
nums[mid] < nums[right]，这意味着中间元素位于旋转点的右侧，最小值应该位于中间元素的左侧或者就是中间元素本身，所以我们可以将右边界移动到mid。 - 如果
nums[mid] == nums[right]，我们不能确定最小值位于中间元素的左侧还是右侧。但是我们可以缩小右边界，因为即使nums[right]是最小值，它也不是唯一的最小值（因为nums[mid]与nums[right]相等）。所以我们可以将右边界移动到right - 1，以帮助缩小搜索范围，同时保持最小值在搜索范围内。
通过这种方式，我们可以在 O(log n) 的时间内找到旋转数组的最小值，同时保持空间复杂度为 O(1)。
