leetcode 81. Search in Rotated Sorted Array II (有重复元素的旋转数组找给定值)

Posted by 111qqz on Wednesday, April 5, 2017

TOC

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).

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

The array may contain duplicates.

好像阿里一面的时候问过。。。

思路:肯定是二分。。。不过由于有重复元素。。。所以很恶心。。。

总的思路是。。。当发现重复元素。。并且该重复元素不是target的时候。。。缩小范围。。。

/* ***********************************************
Author :111qqz
Created Time :2017年04月05日 星期三 20时26分25秒
File Name :81.cpp
************************************************ */



class Solution {

public:

    bool search(vector<int>& nums, int target) {
    int siz = nums.size();
    if (siz==0) return false;
    int l = 0 ;
    int r = siz-1;
    while (l<=r)
    {
        int mid = (l+r)>>1;
        if (nums[mid]==target)  return true;
        if (nums[l]<nums[mid])
        {
        if (nums[l]<=target&&target<nums[mid])
            r = mid - 1;
        else 
            l = mid + 1;
        }
        else if (nums[mid]<nums[r])
        {
        if (nums[mid]<target&&target<=nums[r]) l = mid + 1;
        else r = mid -1;
        }
        else if (nums[l]==nums[mid]) l++;
        else if (nums[mid]==nums[r]) r--;   //nums[l]或nunms[r] is not the target,so remove it..重复元素最烦人了。。。
    }

    return false;

    }

};

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付