算法:数字在排序数组中出现的次数

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

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

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

分析

注意到, 数组是有序的, 可以先通过二分找到其中出现的任意一个的索引

然后计算这个这个索引左右两侧的个数即可.

代码

import java.util.Arrays;
public class Solution {
    public int GetNumberOfK(int[] array, int k) {
        int index = Arrays.binarySearch(array, k);
        if (index < 0) return 0;
        return findLeft(array, index - 1, k) + findRight(array, index + 1, k) + 1;
    }

    private int findLeft(int[] arr, int i, int aim) {
        int res = 0;
        for (; i >= 0 && arr[i] == aim; i--) {
            res++;
        }
        return res;
    }

    private int findRight(int[] arr, int i, int aim) {
        int res = 0;
        for (; i < arr.length && arr[i] == aim; i++) {
            res++;
        }
        return res;
    }
}