[Leetcode]Find Minimum in Rotated Sorted Array

题目描述:

LeetCode 153. Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

题目大意:

假设一个排好序的数组在某处执行了一次“旋转”,找出最小的元素(数组元素不重复)

解题思路:

二分法( 复杂度O(logn) ),实测数据比较水,线性枚举( 复杂度O(n) )也可以。

Python代码:

二分法(20160523增补,感谢网友null122提醒):

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low, high = 0, len(nums) - 1
        while low < high:
            mid = (low + high) / 2
            if nums[mid] <= nums[high]: #min位于左侧上升沿
                high = mid
            else: #min位于左侧上升沿与右侧上升沿之间
                low = mid + 1
        return nums[low]

二分法(原始版本):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        ans = num[0]
        size = len(num)
        low, high = 0, size - 1
        while low <= high:
            mid = (low + high) / 2
            if num[mid] <= num[high]: #min位于左侧上升沿
                high = mid - 1
            else: #min位于左侧上升沿与右侧上升沿之间
                low = mid + 1
            ans = min(ans, num[mid])
        return ans

线性枚举:

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        return min(num)

 

本文链接:http://bookshadow.com/weblog/2014/10/16/leetcode-find-minimum-rotated-sorted-array/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. Andrew Chen Andrew Chen 发布于 2015年3月13日 11:20 #

    不错,赞一个。

  2. test test 发布于 2016年2月10日 12:54 #

    [6,1,2,3,4,5]

  3. null122 null122 发布于 2016年5月22日 17:57 #

    class Solution(object):

    def findMin(self, nums):
    left, right = 0, len(nums) - 1
    result = nums[0]
    while left < right:
    mid = (right + left) / 2
    if nums[mid] < nums[right]:
    right = mid
    else:
    left = mid + 1
    return nums[left]

    你写的不好

  4. 在线疯狂 在线疯狂 发布于 2016年5月23日 12:10 #

    感谢提醒,已经在博文中做了修改。 :)

张贴您的评论