题目
搜索旋转排序数组 II
跟进“搜索旋转排序数组”，假如有重复元素又将如何？
是否会影响运行时间复杂度？
如何影响？
为何会影响？
写出一个函数判断给定的目标值是否出现在数组中。
样例
给出[3,4,4,5,7,0,1,2]和target=4，返回 true
解题
直接法
class Solution:
"""
@param A : an integer ratated sorted array and duplicates are allowed
@param target : an integer to be searched
@return : a boolean
"""
def search(self, A, target):
# write your code here
if target in A:
return True
return False
如果二分法岂不是好多判断条件
public class Solution {
/**
* param A : an integer ratated sorted array and duplicates are allowed
* param target : an integer to be search
* return : a boolean
*/
public boolean search(int[] A, int target) {
// write your code here
if(A == null || A.length == 0)
return false;
for(int i = 0;i<A.length;i++){
if(A[i] == target)
return true;
}
return false;
}
}
半个二分
三个数相等的适合线性查找
public class Solution {
/**
* param A : an integer ratated sorted array and duplicates are allowed
* param target : an integer to be search
* return : a boolean
*/
public boolean search(int[] A, int target) {
// write your code here
if(A==null)
return false;
int n = A.length -1;
return search(A,0,n,target);
}
public boolean search(int[] A,int left,int right,int target){
if(left>right)
return false;
if(A[left] == target || A[right] == target)
return true;
int i = left;
int j = right;
while(i<=j){
int mid = (i+j)>>1;
// 线性查找
if(A[i]==A[j]&&A[i]==A[mid])
return searchLine(A,i,j,target);
if(A[mid] == target){ // 相等
return true;
}else if(A[mid] <= A[right]){ // i mid j right mid在右边升序的序列中
if(A[mid] == A[right])
return search(A,i+1,mid-1,target);
else
return search(A,i+1,mid-1,target) || search(A,mid+1,j,target);
}else {
return search(A,i+1,mid-1,target);
}
}
return false;
}
// 线性查找
public boolean searchLine(int[] A,int i,int j,int target){
for(;i<=j;i++)
if(A[i] ==target)
return true;
return false;
}
}