题目描述
统计一个数字k在排序数组中出现的次数。
第一种
首先想到的就行遍历数组，统计数字。但是如果数字k在数组中不存在或者最后是数组中的最后一位，则需要遍历整个数组，时间复杂度为O(n)。
代码
public int GetNumberOfK(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)
break;
if(array[i] == k){
count++;
}
}
return count;
}
第二种
因为数组的有顺序的，所以可以借助二分法来查找数组中第一次出现和最后一次出现这个k的位置。
判断K第一次出现的位置。二分法将K与中间位置的数字A进行比较，若K正好等于A，需要判断A是否为K的起始位置，若是则返回A的下标；若不是则起始位置在数组的前半段(end = mid -1)。若K>A，则证明起始位置在数组的后半端；若K<A，则证明起始位置在数组的前半段。
其中，若K正好等于A，如何判断A(A的下标为J)是否为K的起始位置（两种情况）
1）若J是数组的0下标说明是起始位置
2）J不是数组的0下标，同时数组的(J+1)的位置不是K
同理也可以通过二分法找K最后一次的位置。
代码
// 采用二分法寻找k第一次出现的位置 递归的方法
public int getFirstIndex(int[] array, int k, int start, int end) {
if(start > end){
return -1;
}
int mid = (start + end) / 2;
if(k == array[mid]){ // k=array[mid]
// 判断mid是不是k第一次出现的位置
if(mid == 0 || (mid > 0 && array[mid -1] != k)){ // mid是k第一次出现的位置
return mid;
}else {
end = mid - 1;
}
}else { // k!=array[mid]
if(array[mid] > k){ // k在数组的前半段
end = mid - 1;
}else { // k在数组的后半段
start = mid + 1;
}
}
return getFirstIndex(array, k, start, end);
}
// 采用二分法寻找k最后一次出现的位置 循环的方法
public int getLastIndex(int[] array, int k, int start, int end) {
int mid;
while(start <= end){
mid = (start + end) / 2;
if(array[mid] == k){
if(mid == array.length - 1 || (mid < array.length - 1 && array[mid+1] != k)){
return mid;
}else {
start = mid + 1;
}
}
if(array[mid] > k){
end = mid - 1;
}else {
start = mid + 1;
}
}
return - 1;
}
public int GetNumberOfK(int [] array , int k) {
if(array.length == 0){
return 0;
}
int firstIndex = getFirstIndex(array, k, 0, array.length-1);
int lastIndex = getLastIndex(array, k, 0, array.length-1);
int count = 0;
if(firstIndex != -1 && lastIndex != -1){
count = lastIndex - firstIndex + 1;
}
return count;
}
