题目链接

牛客网

题目描述

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

Input:
nums = 1, 2, 3, 3, 3, 3, 4, 6
K = 3

Output:
4

解题思路

排序数组记住二分查找

public class Solution {
   
    public int GetNumberOfK(int [] array , int k) {
   
       if (array==null || array.length==0) return 0;
        int first = binarySearch(array, k);
        int last = binarySearch(array, k+1);
        if (first==array.length || array[first]!=k) return 0;
        else return last-first;
    }
    // 找到>=target的元素最先出现的位置
    private int binarySearch(int[] array, int target) {
   
        int l = 0, h = array.length; // 注意这里h取到array.length，可以减少一次对last的判断
        while (l < h) {
   
            int m = l + (h-l)/2;
            if (array[m] >= target) h=m;
            else l = m+1;
        }
        return l;
    }
}