數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
題目描述
統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)喉镰。
public class Solution {
/*解題思路：
有序數(shù)組的問題，采用二分查找懒叛。找到第一個K和最后一個K辅斟，兩者的位置相減
*/
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){//重點array[mid-1] == k
return getFirstK(array, k, start, mid-1);
}else{
return mid;
}
}
//循環(huán)寫法
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){//重點array[mid+1] == k
start = mid+1;
}else{
return mid;
}
mid = (start + end) >> 1;
}
return -1;
}
}
