作者:yulongguxiang | 来源:互联网 | 2023-05-19 06:14
题目描述:统计一个数字在排序数组中出现的次数。publicclassSolution{*思路1:看到排序数组就想到二分法查找,当查找到数字K,再向左右顺序遍历,找到第
题目描述:统计一个数字在排序数组中出现的次数。
public class Solution { /*
思路1:看到排序数组就想到二分法查找,当查找到数字K,再向左右顺序遍历,找到第一个和
最后一个K,然后计算个数,但是K可能出现O(N)次,所以和从头到尾的遍历是一样的
时间复杂度;
思路2:那么我们可以直接用二分查找法直接找到第一个和最后一个K
一下是思路2的实现
*/
public int GetNumberOfK(int [] array , int k) {
if(array == null || array.length == 0){
return 0;
}
int first = GetFirstK(array,k,0,array.length-1);
int last = GetLastK(array,k,0,array.length-1);
return (last-first+1);
}
public int GetFirstK(int [] array , int k, int begin , int end ) {
if(begin > end){
return 0;
}
int meddle = (begin + end)/2;
if(array[meddle] > k){
return GetFirstK(array , k, begin , meddle-1 );
}
else if(array[meddle] return GetFirstK(array , k, meddle+1 ,end);
}
else{
if((meddle-1)<0 || array[meddle-1] != k){
return meddle;
}
else{
return GetFirstK(array , k, begin , meddle-1);
}
}
}
public int GetLastK(int [] array , int k, int begin , int end ) {
if(begin > end){
return -1;
}
int meddle = (begin + end)/2;
if(array[meddle] > k){
return GetLastK(array , k, begin , meddle-1 );
}
else if(array[meddle] return GetLastK(array , k, meddle+1 ,end);
}
else{
if((meddle+1)==array.length || array[meddle+1] != k){
return meddle;
}
else{
return GetLastK(array , k, meddle+1 ,end);
}
}
}
}