排序数组中某个数的个数 38
找到第一个K，找到最后一个K
? ?
通过二分法查找，时间复杂度能降到logn
? ?
如果中间的数小于k，那么在前半段找k
如果中间的数大于k，那么在后半段找k
? ?
找第一个k的时候判断方式如下：
如果中间的数等于k，那么先判断前一个数是否存在，如果存在且等于k，在前半段找
如果存在不等于k或者不存在，那么这个数就是第一个k
? ?
找最后一个k的时候判断方式如下：
如果中间的数等于k，那么先判断后一个数是否存在，如果存在且等于k，在后半段找，如果存在不等于k或者不存在，那么这个数就是最后一个k
? ?
? ?
package getNumOfK;
? ?
public class GetNumOfK {
? ?
int getLastK(int[] data,int length,int k,int start,int end){
? ?
if (start>end) {
return -1;
}
? ?
int midIndex=(start+end)/2;
int midData=data[midIndex];
if (data[midIndex]==k) {
if( (midIndex<length-1&&data[midIndex+1]!=k)||midIndex==length-1) {
return midIndex;
}else {
start=midIndex+1;
}
}else if (midData<k) {
start=midIndex+1;
}else {
end=midIndex-1;
}
return getLastK(data,length,k,start,end);
? ?
}
int getFirstK(int[] data,int length,int k,int start,int end){
if (start>end) {
return -1;
}
? ?
int midIndex=(start+end)/2;
int midData=data[midIndex];
if (data[midIndex]==k) {
if( (midIndex>0&&data[midIndex-1]!=k)||midIndex==0) {
return midIndex;
}else {
end=midIndex-1;
}
}else if (midData>k) {
end=midIndex-1;
}else {
start=midIndex+1;
}
return getFirstK(data,length,k,start,end);
? ?
}
? ?
int getNumOfK(int[] data,int length,int k){
int result = 0;
if (data!=null&&length>0) {
int first=getFirstK(data, length, k, 0, length-1);
int last=getLastK(data, length, k, 0, length-1);
System.out.println(first);
System.out.println(last);
if (first>-1&&last>-1) {
result=last-first+1;
}
}
return result;
? ?
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] testArray={1,2,5,6,6,6,7};
GetNumOfK test=new GetNumOfK();
System.out.println(test.getNumOfK(testArray,6,6));
}
? ?
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
