【题目】统计一个数字在排序数组中出现的次数。
package com.exe9.offer; /**
* 【题目】统计一个数字在排序数组中出现的次数。
* @author WGS
*
*/
public class GetNumOfK {
public int getNumOfK(int[] arr,int target){
if(arr==null || arr.length<=0) return -1;
int len=arr.length;
int count=0; int lastIndex=findLastK(arr, target, 0, len-1);
System.out.println("==="+lastIndex);
if(lastIndex==-1)
return -1;
int firstIndex=findFirstK(arr, target, 0, len-1);
System.out.println("==="+firstIndex); if(firstIndex>=0 && lastIndex>=0)
count=lastIndex-firstIndex+1; return count; } //先寻找重复数字出现在最左边的位置
public int findFirstK(int[] arr,int target,int start,int end){
if(start>end) return -1; int midIndex=(start+end)/2;
int midVal=arr[midIndex]; if(midVal==target){
while(midVal==target){
midIndex--;
midVal=arr[midIndex];
}
return midIndex+1;
}else if(midVal<target){
start=midIndex+1;
}else{//midVal>target
end=midIndex-1;
} return findFirstK(arr,target,start,end); }
////先寻找重复数字出现在最右边的位置
public int findLastK(int[] arr,int target,int start,int end){
if(start>end) return -1;
int midIndex=(start+end)/2;
int midVal=arr[midIndex]; if(midVal==target){
while(midVal==target){
midIndex++;
midVal=arr[midIndex];
}
return midIndex-1;
}else if(midVal<target){
start=midIndex+1;
}else{//midVal>target
end=midIndex-1;
} return findFirstK(arr,target,start,end); } public static void main(String[] args) {
int[] arr=new int[]{1};
GetNumOfK g=new GetNumOfK();
int num=g.getNumOfK(arr, 3);
System.out.println(num); } }