[LeetCode] Search in Rotated Sorted Array II

Search in Rotated Sorted Array II


Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

解题思路:

同Search in Rotated Sorted Array一样,这道题也可以用二分查找。不同的是,这道题元素可以相同,因此,在最坏的情况下时间复杂度为O(n)。

在每次二分查找之前,先压缩左右区间。然后判断:

1、当nums[left]、nums[middle]、nums[right]之一与target相同时,返回true

2、当target<nums[middle]时,分middle在大部还是小部两种情况:

(1)若middle在大部,即nums[middle] > nums[left],则看nums[left]的大小。若nums[left]>target,那么left~middle可以排除,让left=middle+1。若nums[left]<target,那么target的值只能存在left~middle之间,让right=middle - 1

(2)若middle在小部,即nums[middle] < nums[left],那么middle~right可以排除,令right = middle - 1

3、同样,当target>nums[middle]时,分middle在大部还是小部两种情况:

(1)若middle在大部,即nums[middle]>nums[left],那么left~middle可以排除,令left=middle + 1

(2)若middle在小部,即nums[middle]<nums[left]。如果nums[right]>target,那么target可定在middle~right之间,令left=middle+1。否则,nums[right]<target,那么可以排除middle~right之间的元素,令right = middle - 1

下面是代码:

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int len = nums.size();
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            while(left < right && left<len - 1 && nums[left] == nums[left+1]){
                left++;
            }
            while(left < right && right>=1 && nums[right] == nums[right-1]){
                right--;
            }
            int middle = (left + right) / 2;
            if(target == nums[middle] || target == nums[left] || target == nums[right]){
                return true;
            }else if(target < nums[middle]){
                if(nums[middle]>nums[left]){   //表明middle在大部
                    if(nums[left] > target){
                        left = middle + 1;
                    }else{
                        right = middle - 1;
                    }
                }else{                          //表明middle在小部
                    right = middle - 1;
                }
            }else{
                if(nums[middle]>nums[left]){   //表明middle在大部
                    left = middle + 1;
                }else{                          //表明middle在小部
                    if(nums[right]>target){
                        left = middle + 1;
                    }else{
                        right = middle - 1;
                    }
                }
            }
        }
        return false;
    }
};


0 条评论

    发表评论

    电子邮件地址不会被公开。 必填项已用 * 标注