算法（48）--数字在升序数组中出现的次数
前言
仅记录学习笔记，如有错误欢迎指正。
题目
给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数要求：空间复杂度 O(1)，时间复杂度 O(logn)
示例：
-
输入：[1,2,3,3,3,3,4,5],3 输出: 4
解法
有序要想到二分查找！2022加油~public class Solution {
public int GetNumberOfK(int [] array , int k) {
//看见有序，肯定就是二分查找了
int len = array.length;
if(len == 0){
return 0;
}
int firstNum = getFirst(array,k,0,len-1);
int lastNum = getLast(array,k,0,len-1);
if(firstNum != -1 && lastNum != -1){
return lastNum - firstNum + 1;
}
return 0;
}
//递归写法
public int getFirst (int[] array,int k,int start,int end){
if(start > end){
return -1;
}
int mid = (start + end) >> 1;//除以2的n次方
if(k < array[mid]){
return getFirst(array,k,start,mid-1);
}else if(k > array[mid]){
return getFirst(array,k,mid+1,end);
//可能存在重复的 找到左边的第一个
}else if(mid-1 >= 0 && array[mid-1] == k){
return getFirst(array, k, start, mid-1);
}else{
return mid;
}
}
//循环写法
public int getLast (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的值
mid = (start + end) >> 1;
}
return -1;
}
}
