首页 > 代码库 > 【Leetcode】Search in Rotated Sorted Array II
【Leetcode】Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array":
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.
出现相等元素之后会出现一种特殊退化的情况，即中间元素等于start，end的元素，这样无法判断左边或者右边是否出现突增，增减，所以这种情况下必须递归两边，算法退化成线性比较。
1st （3 tries）
class Solution {public: bool search(int A[], int n, int target) { if(A[0] < A[n-1]) return binary_search(A,0,n-1,target); else return ordinary_search(A,0,n-1,target); } bool binary_search(int A[],int start,int end,int target) { if(start > end) return false; int mid = (start + end)/2; if(A[mid] == target) return true; if(A[mid] > target) { return binary_search(A,start,mid-1,target); } else { return binary_search(A,mid+1,end,target); } } bool ordinary_search(int A[],int start,int end,int target) { if(start > end) return false; int mid = (start + end)/2; if(A[mid] == target) return true; /**this is new**//**test case 1,3,1,1,1 or 1,1,1,3,1 无法断定3的具体位置**/ if(A[start] == A[mid] && A[mid] == A[end]) { return ordinary_search(A,start,mid-1,target)||ordinary_search(A,mid+1,end,target); } else if(A[start] <= A[mid]) { if(target <= A[mid] && target >= A[start]) { return binary_search(A,start,mid-1,target); } else { return ordinary_search(A,mid+1,end,target); } } else { if(target >= A[mid] && target <= A[end]) { return binary_search(A,mid+1,end,target); } else { return ordinary_search(A,start,mid-1,target); } } }};
2nd （3 tries）
class Solution {public: bool search(int A[], int n, int target) { //if exists equal so don‘t know whether left or right is available??? return search(A,0,n-1,target); } bool search(int A[], int start, int end, int target) { if(start > end) return false; int mid = start + (end - start)/2; if( A[mid] == target ) return true; else if( A[mid] > target ) { //two side??? if( A[start] == A[end] ) { return search(A,start,mid-1,target) || search(A,mid+1,end,target); } else { //no rotate,sorted array!!! if( A[start] < A[end] ) { return bsearch(A,start,end,target); } // A[start] > A[end]!!! else { if( A[mid] < A[start] ) { return search(A,start,mid-1,target); } //A[mid] >= A[start] else { if(target >= A[start]) { return bsearch(A,start,mid-1,target); } else { return search(A,mid+1,end,target); } } } } } else { if( A[start] == A[end] ) { return search(A,start,mid-1,target) || search(A,mid+1,end,target); } else { //no rotate,sorted array!!! if( A[start] < A[end] ) { return bsearch(A,start,end,target); } // A[start] > A[end]!!! else { if( A[mid] < A[start] ) { if(target <= A[end]) { return bsearch(A,mid+1,end,target); } else { return search(A,start,mid-1,target); } } //A[mid] >= A[start] else { return search(A,mid+1,end,target); } } } } } //binary search!!! bool bsearch(int A[], int start, int end, int target) { while(start <= end) { int mid = start + (end-start)/2; if(A[mid] == target) return true; else if(A[mid] > target) { end = mid-1; } else { start = mid+1; } } return false; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。