原题链接
不知道为什么这道题会是个中等难度的。
一个时间复杂度为O(n)，不需要额外空间的思路：
因为原数组是有序的，只是在某个未知的点发生了旋转，可以简单认为是两个有序数组的拼接，只需要比较list[i]和list[i+1]，如果list[i+1]<list[i]，可以认为list[i+1]是数组中最小的值。
需要考虑到的特殊情况有两个：
- 数组未旋转
- 数组为空
贴上代码：
class Solution:
"""
@param nums: a rotated sorted array
@return: the minimum number in the array
"""
def findMin(self, nums):
n = len(nums)
if n<1:
return
for i in range(0, n - 1):
if nums[i+1] < nums[i]:
return nums[i+1]
return nums[0]
网友评论