首页 > 代码库 > Leetcode.154.Find Minimum in Rotated Sorted Array II

Leetcode.154.Find Minimum in Rotated Sorted Array II

  今天是03/01.说实话,我个人非常讨厌二分搜索的题目,原因在于变种的二分搜索总是要理清楚不同情况下的+1,-1

事实上我觉得我可能从来没有愿意去弄清楚,所以在处理这种题目的时候,我一般都很随缘。

描述:

  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.

  I.you can assume there is no duplicate

  II. what if there are duplicates ?

 

解答:

 

  上面关于这道典型的二分搜索的题目,在不重复的情况下,还是非常easy的。引入重复后,在每一次判断前检查一下left和right临近的值

是否不同,如果不同,则回到了不重复的情况,如果相同,则按照区间减小的方向++ 或者 -- 删除完重复值。值得注意的还有两点:

    1.外面的while 要求l<r-1,所以我们操作完l 和 r 之后检查一下是否可以直接跳出while。

    2.可能pivot就在重复值之间,在开始之前我们先把这种可能性去掉。

 

代码:

不重复情况下:

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

 

出现重复情况下:

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

 


 

Leetcode.154.Find Minimum in Rotated Sorted Array II