【leetcode刷题】T9-寻找旋转排序数组中的最小值

木又AI帮

发布于 2019-07-18 16:51:18

3860

发布于 2019-07-18 16:51:18

文章被收录于专栏：木又AI帮木又AI帮

今天分享leetcode第9篇文章，也是leetcode第153题—寻找旋转排序数组中的最小值，地址是：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

【英文题目】（学习英语的同时，更能理解题意哟~）

Suppose an array sorted in ascending order 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.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

【中文题目】

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

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

请找出其中最小的元素。

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

示例 1:

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

【思路】

本题也有两种思路：一是暴力破解，循环遍历甚至直接使用min函数时间复杂度为O(n)；二是考虑使用类似二分查找的方法，时间复杂度为O(log n)。本文主要介绍第二种思路。

为了和二分查找进行比较，我们将最小的数称为target。

数组经过旋转后，会导致最小的数target在数组中间，比如[1, 2, 3, 4, 5]旋转后成为[3, 4, 5, 1, 2]，target所在位置有什么特点呢？target右边的数（若存在）全部小于target左边的数（若存在）。

这样，我们使用二分查找的思想，找到一个数nums[mid]，就可以和nums[0]进行比较，如果nums[mid] >= nums[0]，则target只可能存在mid右边的区间内，反之则存在于mid左边的区间内，以此类推。

但是有一个特殊情况，就是旋转元素个数为0，需满足条件nums[0] < nums[length-1]，直接返回nums[0]即可。

【代码】

python版本

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        l, r = 0, length - 1
        # 旋转个数为0或者只有一个元素
        if nums[l] <= nums[r]:
            return nums[0]
        else:
            while l <= r:
                mid = (l + r) // 2
                # 只要nums[mid] >= nums[0]，说明最小值还在mid后面
                if nums[mid] >= nums[0]:
                    l = mid + 1
                else:
                    r = mid - 1
            return nums[l]

C++版本

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        // 旋转个数为0或者只有一个元素
        if(nums[l] <= nums[r])
            return nums[0];
        while(l <= r){
            int mid = (l + r) / 2;
            // 只要nums[mid] >= nums[0]，说明最小值还在mid后面
            if(nums[mid] >= nums[0])
                l = mid + 1;
            else
                r = mid - 1;
        }
        return nums[l];
    }
};

【总结】