牛客网：NC74 数字在升序数组中出现的次数

有两种解法：

1.使用模拟法

2.使用二分法

 
 
/**
 * @author xienl
 * @description 数字在升序数组中出现的次数
 * @date 2022/6/29
 */
 
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,3,3,3,3,4,5};
        System.out.println(solution.binary(nums, 3));
    }
 
    /**
     * 使用模拟，一步到位
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK(int [] array , int k) {
        if (array.length == 0 || array[array.length - 1] > k || array[0] < k){
            return 0;
        }
 
        int ans = 0;
        for (int i = 0; i < array.length; i ++){
            if (array[i] == k){
                ans++;
            }
            if (array[i] > k){
                break;
            }
        }
        return ans;
    }
 
 
    /**
     * 使用二分法解决
     *      需要找到 k 出现的个数，那么正常的二分查找，只能找到某一个k出现的位置，
     *      那么如果我们找到 k+ 0.5 或者 k-0.5的位置的数，减一下就是我们的结果
     * @param array
     * @param k
     * @return
     */
    public int binary(int [] array , int k) {
        return calculation(array, k + 0.5) - calculation(array, k - 0.5);
    }
 
    private int calculation(int [] array , double k){
        int left = 0, right = array.length - 1;
        while (left <= right){
            int mid = (left + right) >> 1;
            if (array[mid] > k){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}