今日题目链接：数字在升序数组中出现的次数
数字在升序数组中出现的次数
难度：简单
描述
给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
数据范围
0≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100
空间复杂度 O(1)，时间复杂度 O(logn)
举例
解题思路
这道题，可以直接暴力遍历一遍获取所有值等于目标值，但是既然单独写一篇文章肯定不会只讲这一种方法，暴力法比较简单就不多说了，这里主要讲二分法，既然输入的数组是有序的，所以我们就能很自然的想到用二分查找算法。以题目中给的数组为例，一个比较自然的想法是用二分查找先找到一个3，由于要计算的是输出的次数，所以需要在找到的这个3的左右两边分别再进行顺序扫描，进而得到3的个数，这样最坏的情况下时间复杂度仍然是O(n)，和直接顺序扫描的效率相同。
因此，需要考虑怎样更好的利用二分查找算法，由于数组有序，如果知道了第一个k出现的位置和最后一个k出现的位置，那么我们就可以直接算出有多少个k。因此将思路转化为通过二分查找求第一个和最后一个k出现的位置。
以第一个k出现的位置为例，利用二分查找算法可以直接对数组进行二分，而每次总是拿中间的数字和k做比较，如果中间的数字大于k，那么第一个k只有可能出现在左边，下一次直接在数组左半段继续进行二分查找；如果中间的数字小于k，则第一个k只有可能出现在右边，则在右半段再查找；如果中间的数字等于k，我们先判断它前面的一个数字是不是k，如果不是，那么这个中间的数字就是第一个出现的位置，反之，如果中间数字前面的数字是k，那么第一个k仍然在前半段，继续查找。
同理，找最后一个k出现的位置方法类似，可以使用两个函数分别获得。
实现代码（java）
代码语言：javascript复制import java.util.Arrays;
public class Practise_09 {
public static void main(String[] args) {
int[] array = new int[]{1,2,3,3,3,4,5};
int times = getNumberOfK(array,3);
System.out.println("原数组：" Arrays.toString(array));
System.out.println("3出现的次数:" times);
}
//查找第一个K,和最后一个K,返回二者下标相减 1，即k有多少个
public static int getNumberOfK(int[] array,int k ) {
int first = getFirstNumber(array,k);
int last = getLastNumber(array,k);
if(first == -1 || last == -1 ) {
return 0;
}
return last-first 1;
}
//查找第一个K出现时的下标
public static int getFirstNumber(int[] array,int k) {
int result = -1;
if(array==null || array.length==0) {
return result ;
}
int low = 0,high = array.length-1;
while(low <= high) {
int mid = low (high-low)/2;
if(array[mid]<k) { //小于 K
low = mid 1;
}
else if(array[mid]>k) { //大于 K
high = mid - 1;
}
else{ //等于 K的时候，因为我们要找的是第一个k，所以不确定中间的数是不是第一个，所以还要怕都难它前面的一个数
mid = mid - 1;
if(mid<low || array[mid]!=k) {
return mid 1;
}
else {
high = mid;
}
}
}
return result;
}
//查找最后一个K出现时的下标
public static int getLastNumber(int[] array,int k) {
int result = -1;
if(array==null || array.length==0) {
return result ;
}
int low = 0,high = array.length-1;
while(low <= high) {
int mid = low (high-low)/2;
if(array[mid]<k) {
low = mid 1;
}
else if(array[mid]>k) {
high = mid - 1;
}
else{ //上面的函数和这个函数唯一的区别是这里开始
mid = mid 1;
if(mid>high || array[mid]!=k) {
return mid-1;
}
else {
low = mid;
}
}
}
return result ;
}
}
