【每日一题】159. 寻找旋转排序数组中的最小值
2019-05-16 本文已影响0人
Something0124
原题链接
不知道为什么这道题会是个中等难度的。
一个时间复杂度为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]