Difficulty: Medium
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
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.
Subscribe to see which companies asked this question
Hide Tags
Show Similar Problems
------------------------------------------------------------------------------------
------------------------------------------------------------------------------------
Based on the previous "Search in Rotated Sorted Array", when there are duplicates exists, the judgement for two classes will be not correct. e.g.,
1 1 1 1 1 3 1 vector
L m r pointers
in such a case, when target =3, we can't judge target will be left or right as "L m r" are all 1. In this situation, we explore following method:
1 1 1 1 1 3 1 vector
L m r pointers
target=3;
if m=L!=target, we discard the leftmost one, or L++,
if m=r!=target, we discard the rightmost one, or r++;
eventually, the above will become '1 3', or '3 1'.
//////////////////////////////////////
//codes
class Solution {
public:
bool search(vector<int>& nums, int target) {
int n = nums.size(), mid = n / 2;
int l = 0,
r = n - 1;
while (l <= r){
if (target<nums[mid]){
//case 1
if (nums[l] < nums[mid]){
if (target >= nums[l]){//left side
r = mid - 1;
mid = (l + r) / 2;
}
else{//right side
l = mid + 1;
mid = (l + r) / 2;
}
}
//case 2
else if (nums[l] > nums[mid]){//left side
r = mid - 1;
mid = (l + r) / 2;
}
else {
if (r - l
== 1){
if (target == nums[l] || target == nums[r])return true;
else return false;
}
l++;
mid = (l + r) / 2;
}
}
else if (target>nums[mid]){
//case 2
if (nums[r] > nums[mid]){
if (nums[r] >= target){//right side
l = mid + 1;
mid = (l + r) / 2;
}
else{//left side
r = mid - 1;
mid = (l + r) / 2;
}
}
//case 1
else if (nums[r] < nums[mid]){//right side
l = mid + 1;
mid = (l + r) / 2;
}
else {
if (r - l
== 1){
if (target == nums[l] || target == nums[r])return true;
else return false;
}
r--;
mid = (l + r) / 2;
}
}
else return true;
}
return false;
}
};
No comments:
Post a Comment