题目描述
统计一个数字在排序数组中出现的次数。
package new_offer;
/**
* 统计一个数字在排序数组中出现的次数
* @author Sonya
*思路：
*1 暴力遍历 那么有序没有得到体现 复杂度在O(N);
*2 有序 想到二分查找 利用二分查找 得出
*/
public class N37_GetNumberOfK {
public int GetNumberOfK(int [] array , int k) {
int count=0;
for(int i=0;i<array.length;i++) {
if(array[i]==k)count++;
}
return count;
}
public int GetNumberOfK2(int [] array , int k) {
if(array.length==0)return 0;
int count=0;
int start=getfirstk(array,array.length,k,0,array.length-1);
int end=getlastk(array,array.length,k,0,array.length-1);
if(start>-1&&end>-1)count=end-start+1;
return count;
}
//利用二分查找，查找到第一个k值所在位置。
public int getfirstk(int []array,int lenght,int k,int start,int end) {
if(start>end)return -1;
int middleindex=(end+start)/2;
int middledata=array[middleindex];
if(middledata==k) {//如果中间值等于K,判断这个值是否是第一个。
if((middleindex>0&&array[middleindex-1]!=k)||middleindex==0) {
return middleindex;
}
else end=middleindex-1;
}
else if(middledata>k) {
end=middleindex-1;
}
else{
start=middleindex+1;
}
return getfirstk(array,array.length,k,start,end);
}
//利用二分查找，查找到最后一个k值所在位置。
public int getlastk(int []array,int length,int k,int start,int end) {
if(start>end)return -1;
int middleindex=(end+start)/2;
int middledata=array[middleindex];
if(middledata==k) {
if((middleindex<end&&array[middleindex+1]!=k)||middleindex==end) {
return middleindex;
}
else {start=middleindex+1;}
}else if(middledata>k) {
end=middleindex-1;
}else {
start=middleindex+1;
}
return getlastk(array,length,k,start,end);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int []array= {1,2,3,3,3,4,5,6,6,6,9};
N37_GetNumberOfK n37=new N37_GetNumberOfK();
int count=n37.GetNumberOfK(array, 3);
int count2=n37.GetNumberOfK2(array, 3);
System.out.println(count);
System.out.println(count2);
}
}
转载于:https://www.cnblogs.com/kexiblog/p/11174773.html
相关资源：基础电子中的光耦合器的类型介绍
