关关的刷题日记94 – Leetcode 153. Find Minimum in Rotated Sorted Array- 专知

会员服务 ·

关关的刷题日记94 – Leetcode 153. Find Minimum in Rotated Sorted Array

关关

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记94 – Leetcode 153. 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.

题目的意思是给定一个升序排列的数组，该数组在某一个点翻转了，根据翻转后的数组求该数组的最小值。

方法1：通过观察，翻转后的数组，如果某一个数比前一个数小，那么这个数就是数组的最小值，遍历该数组找到最小值，时间复杂度O(n).

class Solution {
public:
    int findMin(vector<int>& nums) {
        int re=nums[0];
        for(int i=0; i<nums.size()-1; ++i)
        {
            if(nums[i]>nums[i+1])
                re=nums[i+1];
        }
        return re;
    }
};

方法2：二分查找法的变形。先判断区间是否是单调递增区间，也就是看l是否小于等于r，如果是的话，l就是所求。如果不是单调递增区间，也就是l比r大：如果mid大于等于l，说明最小值落在右半部分；如果mid比l小，说明最小值落在左半部分，也可能最小值就是mid本身。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l=0, r=nums.size()-1;
        while(l<r && nums[l]>nums[r])
        {
            int mid=(l+r)/2;
            if(nums[mid]>=nums[l])
                l=mid+1;
            else
                r=mid;                
        }
        return nums[l];
    }
};