【每日一题】159. 寻找旋转排序数组中的最小值

2019-05-16  本文已影响0人  Something0124

原题链接
不知道为什么这道题会是个中等难度的。
一个时间复杂度为O(n),不需要额外空间的思路:
因为原数组是有序的,只是在某个未知的点发生了旋转,可以简单认为是两个有序数组的拼接,只需要比较list[i]和list[i+1],如果list[i+1]<list[i],可以认为list[i+1]是数组中最小的值。

需要考虑到的特殊情况有两个:

  1. 数组未旋转
  2. 数组为空

贴上代码:

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]
上一篇下一篇

猜你喜欢

热点阅读