SearchInRotatedSortedArrayII [source code]
public class SearchInRotatedSortedArrayII {
static
/******************************************************************************/
class Solution {
String indent = "";
boolean DEBUG = false;
public boolean search(int[] nums, int target) {
return search (nums, 0, nums.length - 1, target);
}
boolean search (int[] nums, int lo, int hi, int target) {
String old_indent = indent, header = "";
indent += " ";
if (DEBUG) header = String.format ("lo:(%d), hi:(%d) %s", lo, hi, pointArray (nums, new int[] {95, 96}, new int[] {lo, hi}));
if (DEBUG) System.out.printf ("%s%s ENTER\n", indent, header);
boolean res = false;
if (lo >= hi)
res = lo < nums.length && (nums[lo] == target || nums[hi] == target);
else if (nums[lo] == nums[hi]) // HI > LO
res = search (nums, lo, hi - 1, target);
else {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target)
res = true;
else {
if (nums[mid] == nums[lo]) {
res = search (nums, lo + 1, hi, target);
} else if (nums[mid] > nums[lo]) {
// 4,5,6,7,8,0,1
if (target > nums[mid] || target < nums[lo])
res = search (nums, mid + 1, hi, target);
else
res = search (nums, lo, mid - 1, target);
} else {
// 7,9,0,1,2,3,4,5
if (target < nums[mid] || target >= nums[lo])
res = search (nums, lo, mid - 1, target);
else
res = search (nums, mid + 1, hi, target);
}
}
}
if (DEBUG) System.out.printf ("%s%s RETURNS %b\n", indent, header, res);
indent = old_indent;
return res;
}
String pointArray (int[] nums, int[] codes, int[] indices) {
StringBuilder sb = new StringBuilder ();
int pos = 0;
for (int i = 0; i < nums.length; i++) {
if (pos < codes.length && i == indices[pos]) {
sb.append (wrap (nums[i] + "", codes[pos]));
pos++;
} else {
sb.append (nums[i]);
}
sb.append (" ");
}
return sb.toString ();
}
String wrap (String s, int code) {
return (char) 27 + "[" + code + "m" + s + (char) 27 + "[0m";
}
public boolean search2(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (target == nums[mid])
return true;
if (nums[mid] < nums[lo]) {
if (target < nums[mid] || target >= nums[lo])
hi = mid - 1;
else
lo = mid + 1;
} else if (nums[mid] > nums[lo]) {
if (target > nums[mid] || target < nums[lo])
lo = mid + 1;
else
hi = mid - 1;
} else {
lo++;
}
}
return false;
}
}
/******************************************************************************/
public static void main(String[] args) {
SearchInRotatedSortedArrayII.Solution tester = new SearchInRotatedSortedArrayII.Solution();
int[][] inputs = {
{4,5,6,7,0,1,2}, {6}, {2},
{4,5,6,7,0,1,2}, {5}, {1},
{4,5,6,7,0,1,2}, {1}, {5},
{5,1,3}, {5}, {0}, // critical positions of two == against [lo]
{1,3,5}, {1}, {0}, // critical positions of two == against [lo]
};
for (int i = 0; i < inputs.length / 3; i++) {
int[] nums = inputs[3 * i];
int target = inputs[3 * i + 1][0];
boolean ans = inputs[3 * i + 2][0] >= 0;
System.out.println (Printer.separator ());
// boolean output = tester.search2 (nums, target);
boolean output = tester.search (nums, target);
System.out.printf ("[%s] and %d -> %s, expected: %b\n",
Printer.array (nums), target, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
);
}
}
}
感觉是一个看起来有坑的问题, 但是大概看起来感觉好像跟之前第一题区别不大? 当时思考第一题的时候, 如果lo和hi相等, 可能出问题, 是不是这个原因? 大概谢谢看;
因为每一个iteration都想要判断一下是否首尾相等, 所以感觉这一题好像是用recursion好写一些;
果然, 主要需要区分的就是这个首尾相等的情况; 最后的速度是2ms (3%), 不是很好; 注意上面这个代码带有大量的debug信息, 要全都删了(搜索DEBUG, header, indent)才能AC; 虽然速度还是很慢;
没有editorial;
这题题目表述上面应该就是第一题的一个Follow-Up, 而且语言上强调让你分析复杂度; 后面discussion上面大部分的做法都也是类似这个思路;
现在什么都不说, 你觉得复杂度是多少? 其实也很好分析, 这题因为当我们出现首尾想等的时候, 我们直接选择移动一位, 而不是砍一半, 所以最坏情况, 就是一个O(N)的linear的复杂度;
class Solution {
public:
bool search(int A[], int n, int target) {
int lo =0, hi = n-1;
int mid = 0;
while(lo<hi){
mid=(lo+hi)/2;
if(A[mid]==target) return true;
if(A[mid]>A[hi]){
if(A[mid]>target && A[lo] <= target) hi = mid;
else lo = mid + 1;
}else if(A[mid] < A[hi]){
if(A[mid]<target && A[hi] >= target) lo = mid + 1;
else hi = mid;
}else{
hi--;
}
}
return A[lo] == target ? true : false;
}
};
正好展示了一下开区间的写法, 其实都差不多: header不要带等号, 然后lo+1, hi的话直接选mid, 但是不-1;
除开这个以外, 好像并没有需要什么很复杂的其他的处理? 看来是我把问题搞复杂了; 直接在[mid]==hi的时候, 一个缩减范围, 避开这个duplicate的hi就行了;
The solution is very good and it will be all right if we use the express ‘high = mid-1’ to replace ‘high = mid’, besides ‘while(low < high)’ can be replace by 'while(low <= high), so we just need return false at the end. This is my tips, thank you!
开区间写法还有一个我忘记总结的就是, 开区间最后结束的时候, 对应的闭区间是还有1的长度的, 所以不能和闭区间写法那样, 直接就return FALSE;
另外, 这个方法好像如果我们做lo++好像不行? 也就是用[lo]来做pivot可能会出问题;
在思考这个问题的过程中, 发现了一个开区间写法和闭区间写法之间的关系: 当我们在最后接近terminate的时候, 你可以看到开区间是有一个区间长度(开区间对应的闭区间)3 -> 2 -> 1 : temrinate的过程的, 而闭区间则不一定有这种连贯的更新: 可能有2 -> 0 : terminate, 不对:
开区间:
3 -> l -> 2
r -> 1 terminate
2 -> l -> 1 terminate
r -> 1 terminate
闭区间:
3 -> l -> 1
r -> 1
2 -> l -> 0 terminate
r -> 1 terminate
1 -> l -> 0 terminate
r -> 0 terminate
也不知道这个总结实际上能有什么作用, 不过感觉跟这题也没有什么关系;
但是假如用[lo]来作为pivot, 肯定不能看到[mid]==pivot就直接把lo++, 因为比如在长度是2的情况下, [lo]==[mid]是因为lo==mid;
算了, 讲也讲不清楚, 还是最好自己来实现一下;
另外:
I think, this is not completely correct. For example [3, 1], target = 1, since “hi–” can cause wrong answer.
Here is my solution.
http://paste.ubuntu.com/16914208/
感觉他这个分析有问题, [3,1]的时候, 根本不会触发hi--;
class Solution {
public:
int search(vector<int> & nums, int target)
{
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = (r - l) / 2 + l;
if (target == nums[mid]) {
return true;
} else if (nums[l] <= nums[mid]) {
if (nums[l] == nums[mid]) ++l;
else if (target >= nums[l] && target < nums[mid]) {
r = mid - 1;
} else l = mid + 1;
} else if (nums[mid] <= nums[r]) {
if (nums[mid] == nums[r]) --r;
else if (target > nums[mid] && target <= nums[r]) {
l = mid + 1;
} else r = mid - 1;
} else while (1) ;
}
return false;
}
};
这个题目实际上最好还是用iteration来写, 不然用recursion来写的时候这个debug太遭罪了, 看看上面这一堆的utility;
然后回头看了一下, 用[lo]做utility肯定没有问题啊, 我的recursion就是这么写的; 然后上面的search2就是改成iteration的写法, 成功AC, 速度1(8), 非常的快;
我当时认为用[lo]做pivot可能有问题, 是因为, 比如现在是在2 2这样的长度为2的情况下, lo==mid, 所以[lo]==[mid], 这个时候你能不能直接lo++? 一些人的观点是, 这个时候你lo++实际上是破坏了正确的下一个iteration的方向, 因为下一个iteration应该向左; 但是你注意到没有, 下一个iteration就算向左, 本身也就是最后一个iteration了, 到时候是把[lo]和target进行比较, 如果不能成功, 最后也是直接FALSE; 而我们在当前这个2 2的iteration, 你知不知道[lo]和target可不可能相等? 当然知道! 肯定不相等, 不然代码也不可能走到lo++这个branch来: 我们hit是首先判断的;
底下评论就有关于这个问题的撕逼: 只能说还是看的不够深:
@fentoyal said in C++ concise log(n) solution:
That’s because you are comparing mid with high, not mid with low in “if” statements.
If num[mid] == num[high], it can be proved that num[high] can be discarded safely, but nothing can say about num[low]
– you didn’t even check what value num[low] has, how dare you directly discarded it by “low ++”.
Then you may ask, if you use “num[mid] == num[low]” as the condition, can you use low ++?
The answer is also NO. The reason is you can’t know for sure which direction you go by just checking against num[low]
Why so? This is because this array may be rotated and may be not. For rotated array, checking mid against low or high has same effect,
but for unrotated array, you should always go to left (minimum is the first one), and checking low would make you go to the other direction.
Checking high will automatically make you go all the way to the left. In other words, if you use high as the condition, it is same for both
rotated array and unrotated array, but if you use low, the two cases have opposite conditions.
disagree!
It is also a way to use low to checking.
Accept code using low++ ,
bool search(vector<int>& nums, int target) {
int l = 0, h = nums.size() - 1;
while (l < h) {
int mid = l + (h - l) / 2;
if (nums[mid] == target) return true;
if (nums[mid] < nums[l]) {
if (nums[mid] < target && nums[h] >= target) l = mid + 1;
else h = mid - 1;
} else if (nums[mid] > nums[l]) {
if (nums[mid] > target && nums[l] <= target) h = mid - 1;
else l = mid + 1;
} else {// nums[mid] == nums[l]
l++;
}
}
return nums[l] == target;
}
当然这个人感觉自己其实也没搞明白; 我的是闭区间写法, 这个人开区间写法也能成功, 所以这个左边pivot的思路是完全没有问题的;
It’s true… Actually it’s totally no difference with traversal the array directly… Big O are both O(n)
这个就是放屁了, 不能只看WorstCase的;
The idea is the same as the previous one without duplicates
- everytime check if targe == nums[mid], if so, we find it.
- otherwise, we check if the first half is in order (i.e. nums[left]<=nums[mid])
and if so, go to step 3), otherwise, the second half is in order, go to step 4)- check if target in the range of [left, mid-1] (i.e. nums[left]<=target < nums[mid]), if so, do search in the first half, i.e. right = mid-1; otherwise, search in the second half left = mid+1;
- check if target in the range of [mid+1, right] (i.e. nums[mid]<target <= nums[right]), if so, do search in the second half, i.e. left = mid+1; otherwise search in the first half right = mid-1;
The only difference is that due to the existence of duplicates, we can have nums[left] == nums[mid] and in that case, the first half could be out of order (i.e. NOT in the ascending order, e.g. [3 1 2 3 3 3 3]) and we have to deal this case separately. In that case, it is guaranteed that nums[right] also equals to nums[mid], so what we can do is to check if nums[mid]== nums[left] == nums[right] before the original logic, and if so, we can move left and right both towards the middle by 1. and repeat.
class Solution {
public:
bool search(vector
int left = 0, right = nums.size()-1, mid;
while(left<=right)
{
mid = (left + right) >> 1;
if(nums[mid] == target) return true;
// the only difference from the first one, trickly case, just updat left and right
if( (nums[left] == nums[mid]) && (nums[right] == nums[mid]) ) {++left; --right;}
else if(nums[left] <= nums[mid])
{
if( (nums[left]<=target) && (nums[mid] > target) ) right = mid-1;
else left = mid + 1;
}
else
{
if((nums[mid] < target) && (nums[right] >= target) ) left = mid+1;
else right = mid-1;
}
}
return false;
}
};
这个人的思路还是有点清新脱俗的, 他直接更准确的定位了真正造成问题的duplicate情形; 用第一区和第二区来代表rotate的两部分(而不是被mid等分的);
假如mid在第一区, 然后[mid]==[lo], 这个是不会出问题的, 但是假如[mid]在第二区, 但是还是和[lo]相等, 就跟他举的这个例子这样, 这里就有问题了; 如果这个时候不做特殊处理, 直接按照之前做第一题的逻辑去处理, 比如是3,4,1,2,3,3,3,3这样一个例子当中找4, 你比较出来[mid]>=[lo], 所以你认为自己是在第一区, 然后比较target是否在[[lo], [mid])之间, 这个肯定是失败的, 因为他俩相等, 这个决定跟target的具体数值都没有关, 所以你直接就选择了向右走, 那么自然是找不到4的;
这个想法更加的极端:
My answer is similar to yours. But we don’t have to check duplicated items in every loop, instead we check once.
class Solution {
public:
bool search(vector<int>& nums, int target) {
if(nums.size() == 0) return false;
// Find the non-duplicated head: h
int h = 0;
while(h != nums.size()-1 && nums[h] == nums[nums.size()-1]) h++;
// Previous algorithm can deal with duplicated items if the head of array is not a duplicated item
int L = h, R = nums.size()-1, M = (L+R)/2;
while(L < R){
if(nums[M] == target)
return true;
else if((nums[h] <= target) ^ (target <= nums[M]) ^ (nums[M] < nums[h]) == false)
R = M;
else
L = M+1;
M = (L+R)/2;
}
return (L == R && nums[L] == target)? true : false;
}
};
这个观察的比较到位, 只要pivot不是duplicate就行了; 这样保证第一区和第二区没有重合, 那么直接用原来第一题的算法做就行了, 内部的duplicate根本没有关系;
public boolean search(int[] nums, int target) {
int start = 0, end = nums.length - 1, mid = -1;
while(start <= end) {
mid = (start + end) / 2;
if (nums[mid] == target) {
return true;
}
//If we know for sure right side is sorted or left side is unsorted
if (nums[mid] < nums[end] || nums[mid] < nums[start]) {
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
//If we know for sure left side is sorted or right side is unsorted
} else if (nums[mid] > nums[start] || nums[mid] > nums[end]) {
if (target < nums[mid] && target >= nums[start]) {
end = mid - 1;
} else {
start = mid + 1;
}
//If we get here, that means nums[start] == nums[mid] == nums[end], then shifting out
//any of the two sides won't change the result but can help remove duplicate from
//consideration, here we just use end-- but left++ works too
} else {
end--;
}
}
return false;
}
In case anyone wonders, yes I agree that we don’t need to check two parts. It’s just that Doing that can slightly boost the performance, no asymptotic difference though.
不知道为什么要把[mid]和两头的都比, 有区别吗?
For those who have already solved Search in Rotated Sorted Array, this problem can be solved similarly using codes for that problem and simply adding codes to skip the duplicates.
For Search in Rotated Sorted Array, I post solutions in C/C++/Python here (C and C++ only needs 11 lines).
Now, based on the above codes, you can solve this problem by simply adding two lines to skip duplicates both starting from left and right.
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
while (l < r && nums[l] == nums[l + 1]) l++; // skip duplicates from the left
while (r > l && nums[r] == nums[r - 1]) r--; // skip duplicates from the right
int mid = (l + r) / 2;
if (nums[mid] == target) return true;
if (nums[mid] > target) {
if (nums[l] <= target || nums[mid] < nums[l]) r = mid - 1;
else l = mid + 1;
}
else {
if (nums[l] > target || nums[mid] >= nums[l]) l = mid + 1;
else r = mid - 1;
}
}
return false;
}
};
没有之前那个做法聪明, 他每一个iteration都跑一次, 没有意思;
事实上, 只要你一开始从一头skip过一次之后, 第一区和第二区肯定是完全disjoint的, 所以你后面的iteration这两个while循环根本都不会跑; 自己脑子里visual一下应该不难;
submission最优解就是三叉循环的写法, 第三叉移动pivot;
Problem Description
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
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.
Difficulty:Medium
Total Accepted:113.3K
Total Submissions:346.4K
Contributor:LeetCode
Related Topics
arraybinary search
Similar Questions
Search in Rotated Sorted Array