数字在排序数组中出现的次数

---

题目描述

统计一个数字在排序数组中出现的次数。

---

思路：

暴力解：

①定义计数器，遍历
②只要找到相同的target(目标值)，计数器+1
缺点：数组很大时，会做很多无用功

---

具体实现代码如下：

public int GetNumberOfK(int [] array , int k) {
        // 代码的鲁棒性
        if (array == null || array.length == 0){
            return -1;
        }
        // 计数器
        int count = 0;
        for (int num : array){
            if (num == k){
                count++;
            }
        }
        return count;
 }

---

二分查找：

result[ 1, 2, 3, 3, 3, 3, 4, 5, 6] target = 3
①找到第一个 3 出现的位置 start
②找到第二个 3 出现的位置 end
③target 出现的次数为 end - start +1

---

具体实现如下图所示：

---

具体实现代码如下：

public int GetNumberOfK(int [] array , int k) {
        // 代码的鲁棒性
        if (array == null || array.length == 0){
            return -1;
        }
        int start = getFirstK(array,k);
        int end = getLastK(array,k);
        return end-start+1;
    }
    // 第一个 target 出现的位置
    private int getFirstK(int [] array , int k){
        int start = 0;
        int end = array.length-1;
        int mid = (end+start)/2;
        while (start <= end){
            // 注意判断条件：当array[mid] = k时，也要将end指针向左移动 1, 因为此时我们要找的是 第一个 出现的 target
            if (array[mid] < k){
                start = mid +1;
            }else {
                end = mid -1;
            }
            mid = (end+start)/2;
        }
        return start;
    }
    // 最后一个 target 出现的位置
    private int getLastK(int [] array , int k){
        int start = 0;
        int end = array.length-1;
        int mid = (end+start)/2;
        while (start <= end){
            // 注意判断条件：当array[mid] = k时，也要将start指针向有移动 1, 因为此时我们要找的是 最后一个 出现的 target
            if (array[mid] <= k){
                start = mid +1;
            }else {
                end = mid -1;
            }
            mid = (end+start)/2;
        }
        return end;
    }

NowCoder（Online Coding, Please Click）