LeetCode154—Find Minimum in Rotated Sorted Array II

心已赠人 2022-07-15 12:26 88阅读 0赞

## 原题 ##

[原题链接][Link 1]

> Follow up for “Find Minimum in Rotated Sorted Array”:  
> What if duplicates are allowed?
> 
> Would this affect the run-time complexity? How and why?  
> 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.
> 
> The array may contain duplicates.

## 分析 ##

序列中可能有重复的元素。

### 1.朴素解法 ###

仍然是线性搜索，找到不满足**“非递减”**的位置，复杂度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.使用二分查找 ###

假如序列中没有重复元素，用`l`，`r`，`m`分别表示序列的左右中索引。  
那么：  
1.当 `nums[m]<nums[r]` 则说明最小值位于序列的左边，修改`r=m`  
2.当 `nums[m]>nums[r]`则说明最小值位于序列的右边，修改`l=m+1`

这是一般情况，不过当序列中出现重复元素之后，情况就不一样了。  
例如原序列是\{1,3,3,3,3,3,3\}翻转过后可能是\{3,1,3,3,3,3,3\}或者是\{3,3,3,3,3,1,3\}，这样无法判断是在左边还是右边。不能够究竟是截掉左边还是截掉右边，因此，只能对边缘截去一步，最坏情况下，时间复杂度就退化成O(n)了。

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 if(nums[m]<nums[r])
                {
                    r=m;
                }
                else
                {
                    r--;
                }
            }
            return nums[l];
        }
    
    };

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