看到升序数组，那一般来说二分法跑不了 那么这里我提供下我的三种解法，两种二分法，一种hash存储；
1 .两次二分法分别找到第一次出现的该数字和最后一次出现的该数字位置
主要思路，在二分法第一次查到k值的时候判断前面或者后面是否有也等于k值的，以此决定是否要前移或者后移来找到最左或者最右的k值点； 代码：
代码语言：javascript复制public class Solution {
//统计一个数字在排序数组中出现的次数
public int GetNumberOfK(int[] array, int k) {
if (array == null) {
return 0;
}
if (array.length==1&&array[0]==k){
return 1;
}
int firstKIndex = getFirstKIndex(array, k);
int lastKIndex = getLastKIndex(array, k);
return firstKIndex==lastKIndex?0:lastKIndex-firstKIndex 1;
}
public int getFirstKIndex(int[] array, int k){//得到第一个k---右结点向左移动
int left = 0, right = array.length - 1;
int mid = getMid(left, right);
while (left <= right) {
if (array[mid] == k&&mid - 1 >= 0 && array[mid - 1] == k) {
right=mid-1;
} else if (array[mid]> k) {
right = mid-1;
} else if (array[mid] < k) {
left = mid 1;
}else {
return mid;
}
mid = getMid(left, right);
}
return -1;
}
public int getLastKIndex(int[] array, int k){//得到第一个k---左结点向右移动
int left = 0, right = array.length - 1;
int mid = getMid(left, right);
while (left <= right) {
if (array[mid] == k&&mid 1<=array.length-1&& array[mid 1] == k) {
left=mid 1;
} else if (array[mid]> k) {
right = mid-1;
} else if (array[mid] < k) {
left = mid 1;
}else {
return mid;
}
mid = getMid(left, right);
}
return -1;
}
public int getMid(int left, int right) {
return left (right left) / 2;
}
}2. 查找k-0.5和k 0.5来获取这两者之间的数字个数就是k的个数
因为array中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索k-0.5和k 0.5 这两个数应该插入的位置，然后相减即可。
代码：
代码语言：javascript复制 public int GetNumberOfK(int [] array , int k) {
if (array==null||array.length<1){
return 0;
}
return binarySearch(array,k 0.5)-binarySearch(array,k-0.5);
}
private int binarySearch(int[] array, double k) {
int low=0,high=array.length-1;
while (low<=high){
int mid=getMidIndex(low,high);
if (k<array[mid]){
high=mid-1;
}else if (k>array[mid]){
low=mid 1;
}
}
return low;
}
public int getMidIndex(int left,int right){
return left (right-left)/2;
}3.hash
没啥好说的，就是一个普通利用hash随机读取
代码语言：javascript复制 public int GetNumberOfK(int [] array , int k) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : array) {
if (num == k) {
map.put(num, map.getOrDefault(num, 0) 1);
}
}
return map.get(k) == null ? 0 : map.get(k);
}
