题目描述

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

题解一

遍历数组，用一个变量这个数字出现的次数。

时间复杂度为O(n)，空间复杂度为O(1)。

public int GetNumberOfK(int[] array , int k) {
    int count = 0;
    for (int num : array)
        if (num == k) count++;
    return count;
}

题解二

二分查找，先用二分查找算法找到数组中等于k的数字，但是由于k可能有多个。于是分别向左右两边遍历，计算出数组中有多少个数字等于k。

时间复杂度为O(n)，空间复杂度为O(1)。

public int GetNumberOfK(int[] array, int k) {
    int len = array.length;
    if (len == 0)
        return 0;
    int left = 0, right = len-1;
    int begin = 0, end = len-1;
    
    // 二分查找
    while (left <= right) {
        int medium = (left + right) / 2;
        if (array[medium] == k) {
            begin = medium;
            end = medium;
            // 找到与k相等的数字后，分别从左右两边遍历
            while (begin >= 0 && array[begin] == k) begin--;
            while (end < len && array[end] == k)  end++;
        }
        if (begin == 0 && end == len-1)
            return 0;
        if (k < array[medium])
            right = medium - 1;
        else left = medium + 1;
    }
    return end - begin - 1;
}

题解三

题解二的时间主要消耗在如何确定排序数组中的第一个k和最后一个k上，那么是不是可以利用二分查找直接找到第一个k和最后一个k？答案是肯定的。

我们通过两次二分查找找到数组中的第一个k和最后一个k，由于数组是有序的，所以可以直接得到相同数字的个数。

时间复杂度为O(logn)，空间复杂度为O(1)。

public int GetNumberOfK(int[] array, int k) {
    int lower = GetLower(array, k);
    int upper = GetUpper(array, k);
    return upper - lower + 1;
}

private int GetLower(int[] array, int k) {
    int left = 0, right = array.length-1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (k <= array[mid])
            right = mid - 1;
        else left = mid + 1;
    }
    return left;
}

private int GetUpper(int[] array, int k) {
    int left = 0, right = array.length-1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (k >= array[mid])
            left = mid + 1;
        else right = mid - 1;
    }
    return right;
}