方法1:遍历,时间复杂度为O(n);
public static int GetNumberOfK1(int [] array , int k){
if(array.length==0){
return 0;
}
int count=0;
for(int i=0;i<array.length;i++){
if(array[i]==k){
count++;
}
}
return count;
}
方法2:利用二分查找,可以查找k-0.5和k+0.5的下标,做差。就是k在数组中出现的次数
public static int GetNumberOfK2(int[] array,int k){
return binSearch(array,k+0.5)-binSearch(array,k-0.5);
}
public static int binSearch(int[] array,double k){
int start=0;
int end=array.length-1;
while(start<=end){
int mid=start+((end-start)>>1);
if(k<array[mid]){
end=mid-1;
}
else{
start=mid+1;
}
}
return start;
}
方法3:二分查找,用递归二分法找到第一个k和最后一个k,然后得到个数
public static int GetNumberOfK3(int[] array,int k){
int num=0;
if(array.length==0){
return 0;
}
int firstK=getFirstK(array,k,0,array.length-1);
int lastK=getLastK(array,k,0,array.length-1);
if(firstK>=0 && lastK>=0){
num=lastK-firstK+1;
}
return num;
}
//找到第一个出现的数字的下标
public static int getFirstK(int[] array,int k,int start,int end){
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (k <= array[mid])
end = mid - 1;
else
start = mid + 1;
}
if (start < array.length && array[start] == k)
return start;
else
return -1;
}
//找到最后一个出现的数字的下标
public static int getLastK(int[] array,int k,int start,int end){
while(start<=end){
int mid=start+((end-start)>>1);
if(k>=array[mid]){
start=mid+1;
}
else{
end=mid-1;
}
}
if(end>=0 && array[end]==k){
return end;
}
else
return -1;
}