LeetCode153寻找旋转排序数组中的最小值

发表于 | 更新于 | 分类于 |

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

1
2
输入: [3,4,5,1,2]
输出: 1

示例 2:

1
2
输入: [4,5,6,7,0,1,2]
输出: 0

解题思路

这题的核心解题思路就是使用二分查找。

  1. 当得到一个输入数组时，首先比较其首字符与尾字符大小，当首大于尾的话，传入这个数组的最小值就是首字符的值。
  2. 如果第一步中，首大于尾，则最小值可能在数组中间，使用二分查找，分别查找数组的两部分。
  3. 返回这段数组的最小值

代码实现

核心代码实现：GitHub地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def find(nums, init):
    result = init
    if nums[0] <= nums[-1]:
        if nums[0] <= result:
            result = nums[0]
    else:
        result = min(find(nums[0:len(nums) // 2], result), find(nums[len(nums) // 2:], result), result)

    return result

class Solution(object):

    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return find(nums, 999999999)