LeetCode153—Find Minimum in Rotated Sorted Array

不念不忘少年蓝@ 2022-07-15 10:12 84阅读 0赞

## 原题 ##

[原题链接][Link 1]

> 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.

## 分析 ##

原序列是非递减序列，但该序列可能发生`Rotated`，具体操作可以理解为从某个元素开始到最后一个元素全部放到了序列的前面。

### **两种解法** ###

想了两个办法，一个是线性查找，一个是二分查找。

#### **1.线性查找** ####

根据这个序列的性质可能存在两种情况，一是序列根本就没有翻转，那么最小值就是`nums[0]`，另外一种情况就是翻转过，那么翻转过的序列肯定分为左子序列和右子序列，并且分别递增，分界点就在于不满足**“非递减”**这个条件的位置。

由于是线性查找，因此时间复杂度为O(n)

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

#### **2.二分查找** ####

二分查找的效率O(logn)是要高于线性查找。

二分查找的套路就是将序列对半分为两个子序列，那么由性质可知：  
1.如果子序列最左的元素小于子序列的最右元素，说明该子序列是递增的，也就没进行翻转，那么最小值就是最左元素。  
2.否则子序列进行过翻转，这个时候，最小值肯定出现这个子序列中，调整索引值，继续进行折半查找。

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

[Link 1]: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/