Leetcode (154) -- find the minimum value II in the rotation sort array

Leetcode（154）—— Look for the minimum value in the rotation sort array II

subject

We know a length of n Array of , In ascending order in advance , Through 1 To n Time rotate after , Get the input array . for example , Original array nums = [0,1,4,4,5,6,7] After the change may get ：

• If you rotate 4 Time , You can get [4,5,6,7,0,1,4]
• If you rotate 7 Time , You can get [0,1,4,4,5,6,7]

Be careful , Array [a[0], a[1], a[2], …, a[n-1]] Rotate once The result is an array [a[n-1], a[0], a[1], a[2], …, a[n-2]] .

Give you a chance to exist repeat An array of element values nums , It turns out to be an ascending array , According to the above situation, we have made many rotations . Please find and return the The smallest element .

You must minimize the steps of the whole process .

Example 1：

Input ：nums = [1,3,5]
Output ：1

Example 2：

Input ：nums = [2,2,2,0,1]
Output ：0

Tips ：

• n == nums.length
• $1$ <= n <= $5000$
• $-5000$ <= nums[i] <= $5000$
• nums It turns out to be an ascending array , And carried on $1$ to $n$ Second rotation

Advanced ： This problem is related to Look for the minimum value in the rotation sort array similar , but nums It may contain repeating elements . Does allowing repetition affect the time complexity of the algorithm ？ How will it affect , Why? ？

Answer key

Method 1 ： Two points search

Ideas

​​   Rotate sort array $nums$ Probably Split into 2 A sort array $nums1,nums2$, also $nums1$ Any element $>=nums2$ Any element ; therefore , Consider dichotomy to find the dividing point of these two arrays $nums[i]$ ( That is to say 2 The first element of an array ).
​​   Set up leftleft, rightright Pointer in numsnums Both ends of the array ,midmid It's the midpoint of every two minutes ：

• When $nums[mid]>nums[right]$ when ,$mid$ It must be in the 1 In a sorted array ,$i$ Must be satisfied with $mid<i<=right$, So execute $left=mid+1$;
• When $nums[mid]<nums[right]$ when ,$mid$ It must be in the 2 In a sorted array ,$i$ Must be satisfied with $left<i<=mid$, So execute $right=mid$;
• When $nums[mid]==nums[right]$ when , It's a comparison of this question 153 topic The difficulties of （ The reason is that the elements of the array in this question can be repeated , It's hard to judge the dividing point ii Pointer interval ）;
  • for example $[1,0,1,1,1]$ and $[1,1,1,0,1]$, stay $left=0,right=4,mid=2$ when , Unable to judge $mid$ In which sort array .
  • We use Make one end of the same end move the subscript until the new $l$ and $r$ The values of , To solve this problem （ That is to restore dichotomy ）, prove ：
    • This operation will not make the array out of bounds ： Because the iteration condition guarantees right > left >= 0;
    • This operation will not cause the minimum value to be lost ： hypothesis nums[right]nums[right] Is the minimum , There are two situations ：
    • if $nums[right]$ Is the only minimum ： Then it is impossible to meet the judgment conditions $nums[mid]==nums[right]$, because mid < right（left != right And mid = (left + right) // 2 Rounding down ）;

Code implementation

Leetcode Official explanation ：

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

My own ：

class Solution {
    
public:
    int findMin(vector<int>& nums) {
    
        if(nums.size() == 1) return nums[0];
        int l = 0, r = nums.size() - 1, mid;
        //  Subtract duplicate values , Restore secondary , But you can't delete them all , Keep the same number at least 1 individual （ and  81  The questions are different ）
        while(nums[l] == nums[r] && l < r) l++; //  avoid [1,1]
        while(l <= r){
    
            mid = (l+r)/2;
            if(nums[l] <= nums[r]) break;
            else{
    
                if(nums[mid] >= nums[l]) l = mid + 1;   //  Delete the left section 
                else r = mid;   //  Delete the right section 
            }
        }
        return nums[l];
    }
};

Complexity analysis

Time complexity ： Resuming secondary processing , At worst （ Consider that the whole array is the same number ） Complexity is $O(n)$, The next step is to find the rotation point 「 Two points 」, The complexity is $O(logn)$. The overall complexity is $O(n)$ Of .
Spatial complexity ：$O(1)$