博文中会简要介绍Leetcode P0081题目分析及解题思路。
“Remove Duplicates from Sorted Array II”是p0033的变形题，边界条件比它的原型题要复杂一些，因为有重复的元素。
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.
根据原型题的思路，我们其实只需要重点关注一个情况，即当mid指针指向的位置上的元素和两端位置上的元素都一样的时候，我们需要在mid指针两边都搜索。核心思路在Java代码中已经注释。
以下是Java的题解代码实现。
class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0)
return false;
return this.binarySearch(nums, 0, nums.length-1, target);
}
private boolean binarySearch(int[] nums, int left, int right, int target) {
if (left > right)
return false;
int mid = (left+right)/2;
if (nums[mid] == target)
return true;
// 左右指针和mid指针指向的元素都相同，则mid指针左右部分都需要搜索
else if (nums[mid] == nums[left] && nums[mid] == nums[right]) {
return this.binarySearch(nums, mid+1, right, target) || this.binarySearch(nums, left, mid-1, target);
}
// 落在升序序列上，按普通的二分查找移动left和right即可
else if (nums[mid] >= nums[left] && nums[mid] <= nums[right]) {
if (nums[mid] < target)
return this.binarySearch(nums, mid+1, right, target);
else
return this.binarySearch(nums, left, mid-1, target);
}
// 落在左半边升序序列
else if (nums[mid] >= nums[left] && nums[mid] > nums[right]) {
if (nums[mid] > target && target >= nums[left])
return this.binarySearch(nums, left, mid-1, target);
else
return this.binarySearch(nums, mid+1, right, target);
}
// 落在右半边升序序列
else if (nums[mid] < nums[left] && nums[mid] <= nums[right]) {
if (nums[mid] < target && target <= nums[right])
return this.binarySearch(nums, mid+1, right, target);
else
return this.binarySearch(nums, left, mid-1, target);
}
return false;
}
}
以下是C++的题解代码实现。
class Solution {
public:
bool search(vector<int>& nums, int target) {
if (nums.size() == 0)
return false;
return this->BinarySearch(nums, 0, nums.size()-1, target);
}
private:
bool BinarySearch(vector<int>& nums, int left, int right, int target) {
if (left > right)
return false;
int mid = (left+right)/2;
if (nums[mid] == target)
return true;
// 左右指针和mid指针指向的元素都相同，则mid指针左右部分都需要搜索
else if (nums[mid] == nums[left] && nums[mid] == nums[right]) {
return this->BinarySearch(nums, mid+1, right, target) || this->BinarySearch(nums, left, mid-1, target);
}
// 落在升序序列上，按普通的二分查找移动left和right即可
else if (nums[mid] >= nums[left] && nums[mid] <= nums[right]) {
if (nums[mid] < target)
return this->BinarySearch(nums, mid+1, right, target);
else
return this->BinarySearch(nums, left, mid-1, target);
}
// 落在左半边升序序列
else if (nums[mid] >= nums[left] && nums[mid] > nums[right]) {
if (nums[mid] > target && target >= nums[left])
return this->BinarySearch(nums, left, mid-1, target);
else
return this->BinarySearch(nums, mid+1, right, target);
}
// 落在右半边升序序列
else if (nums[mid] < nums[left] && nums[mid] <= nums[right]) {
if (nums[mid] < target && target <= nums[right])
return this->BinarySearch(nums, mid+1, right, target);
else
return this->BinarySearch(nums, left, mid-1, target);
}
return false;
}
};