[LeetCode]81. Search in Rotated Sorted Array II

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Follow up:

• This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
• Would this affect the run-time complexity? How and why?

这个题作为33题Search in Rotated Sorted Array的扩展题,或者说变形题. 由原来不存在重复元素的数组,变为存在重复元素的颠倒数组. 其他条件类似, 给定target在数组中查找这个target, 存在,返回true,不存在返回false.

Solution

Analysis

由于重复元素的存在, nums[mid]和nums[right]之间就并不仅仅是大下关系了, 两者有可能相等. 但是判断条件nums[mid] < nums[right]如果满足,那么这个子区间一定是有序的, 此外, 如果两者相等, 因为之前已经判断过nums[mid]和target之间的对等关系, 所以我们可以确定nums[right]!=target. 所以,可以变换right的范围,让right自减. 其他情况就类似.

具体实现,看代码.

Code

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        // nums[mid] <= nums[right]: 不能保证[mid, right]为递增序列
        //eg: [1,1,3,1]: 细分分成nums[mid] < nums[right];
        // nums[mid] == nums[right]: 不能确定,因为mid肯定不是,
        // 那么right对应位置也不是, 跳过right
        
        while (left <= right){
            int mid = left + (right - left)/2;
            
            if (nums[mid] == target)
                return true;
            else if (nums[mid] < nums[right]){
                if (nums[mid] < target && nums[right] >= target)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            else if (nums[mid] > nums[right]){
                if (nums[left] <= target && nums[mid] > target)
                    right = mid -1;
                else
                    left = mid + 1;
            }
            else
                right--;
        }
        return false;
    }
};

推荐文章（由hexo文章推荐插件驱动）

• [LeetCode]4. Median of Two Sorted Arrays
• [LeetCode]33. Search in Rotated Sorted Array
• [LeetCode]33. Search in Rotated Sorted Array