题解 |数字在升序数组中出现的次数

解法一：暴力

• 在一个数组中寻早某个元素或者统计其出现的次数
• 显而易见的方法是暴力解法
• 循环枚举数组元素，如果有找到目标值K，加入计数器
• 返回计数器数值即可

Java参考代码：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       //暴力解法：遍历数组，找到目标数字计数器加一
        int ans=0;
        for(int i=0;i<array.length;i++){
            //找到目标数字计数器加一
            if(array[i]==k){
                ans++;
            }
        }
        //返回结果
        return ans;
    }
}

复杂度分析：

时间复杂度：O(N) N 为数组长度，最坏情况下暴力一遍数组。

空间复杂度：O(1) 常数空间的复杂度

解法二：二分查找

• 经典的二分范围查找题目
• 注意数组已经排序，可以想到用二分查找
• 下界定义为：如果存在目标值，则指向第一个目标值，否则，如果不存在， 则指向大于目标值的第一个值。
• 上界定义为：不管目标值存在与否，都指向大于目标值的第一个值。

Java参考代码：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        //
        int leftIndex = binarySearch(array