题解 | #旋转数组的最小数字#
旋转数组的最小数字
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
解题思路
二分法。
- 如果中点处的值大于右边界的值,则最小值在中点右边,更新左边的边界;
- 如果中点处的值小于右边界的值,则最小值在中点的左边或者是中点,更新右边界的值;
- 如果相等的话,则逐步向左减少右边界的值。
- 最终返回结果即可。
复杂度
- 时间复杂度为O(logn);
- 空间复杂度为O(1)。
代码
Python
class Solution: def minNumberInRotateArray(self , nums: List[int]) -> int: left = 0 right = len(nums) - 1 while left < right: mid = (right+left) // 2 if nums[mid] > nums[right]: left = mid + 1 elif nums[mid] == nums[right]: right -= 1 else: right = mid return nums[left]
C++
class Solution { public: int minNumberInRotateArray(vector<int>& nums) { int left = 0, right = nums.size() - 1; while(left < right) { int mid = int((left+right) / 2); if(nums[mid] > nums[right]) { left = mid+1; } else if(nums[mid] < nums[right]) { right = mid; } else { right--; } } return nums[left]; } };