题目描述
统计一个数字在排序数组中出现的次数。
思路
当然可以直接暴力解法：
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int sum =0;
for(int i=0;i<array.length;i++){
if(array[i]==k)
sum++;
}
return sum;
}
}
这也是我直接想到的解法，后来感觉这题没那么简单(╯﹏╰)b，于是看了下网上的解法，果然是如此，题目中强调了数组有序，所以就有一句说法“看见有序，肯定就是二分查找”，下面给出一个很好的二分查找解法，即用到了递归，还给出了循环解法：
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int length = array.length;
if(length == 0){
return 0;
}
// 二分查找
int firstK = getFirstK(array, k, 0, length-1); // 得到最前面的数字
int lastK = getLastK(array, k, 0, length-1); // 得到最后面的数字
if(firstK != -1 && lastK != -1){ // 计算出现的次数，因为数组有序，所以找到一样的值时，中间的值都一样
return lastK - firstK + 1;
}
return 0;
}
//递归写法
private int getFirstK(int [] array , int k, int start, int end){
if(start > end){
return -1;
}
int mid = (start + end) >> 1;
if(array[mid] > k){
return getFirstK(array, k, start, mid-1);
}else if (array[mid] < k){
return getFirstK(array, k, mid+1, end);
}else if(mid-1 >=0 && array[mid-1] == k){
return getFirstK(array, k, start, mid-1);
}else{
return mid;
}
}
//循环写法
private int getLastK(int [] array , int k, int start, int end){
int length = array.length;
int mid = (start + end) >> 1;
while(start <= end){
if(array[mid] > k){
end = mid-1;
}else if(array[mid] < k){
start = mid+1;
}else if(mid+1 < length && array[mid+1] == k){
start = mid+1;
}else{
return mid;
}
mid = (start + end) >> 1;
}
return -1;
}
}