[LeetCode] Search in Rotated Sorted Array II

[LeetCode] Search in Rotated Sorted Array II

分类：c++oj

c++leetcode

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":What ifduplicatesare 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;}};

版权声明：本文为博主原创文章，未经博主允许不得转载。

上一篇[LeetCode] Remove Duplicates from Sorted Array II

顶0踩0

不会因为别人显赫的成功而促使自己有卓越的进步。