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

链接：https://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2?f=discussion
来源：牛客网

题目描述：

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

思路一：

二分查找，然后向前向后找

代码：
时间复杂度O(logn)，空间复杂度O(1)

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0)
            return 0;
        int count = 0;
        int low = 0, high = array.length - 1, mid = 0;
        while(low <= high){
            mid = low + (high -low) / 2;
            if(array[mid] == k)
                break;
            else if(array[mid] > k)
                high = mid - 1;
            else
                low = mid + 1;
        }
        if(low <= high){
            for(int i = mid;i >= 0;i--){
                if(array[i] == k)
                    count++;
                else
                    break;
            }
            for(int i = mid + 1;i < array.length;i++){
                if(array[i] == k)
                    count++;
                else
                    break;
            }
        }
        return count;
    }
}

Runtime：19ms

思路二：（推荐）

看到有序，就应该想到二分查找。找到该数字在数组中第一次、最后一次出现的位置
代码：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0)
            return 0;
        int first = getFirstK(array,k,0,array.length - 1);
        int last = getLastK(array,k,0,array.length - 1);
        if(first == -1 || last == -1)
            return 0;
        else
            return last - first + 1;
    }
    private int getFirstK(int [] array, int k, int low, int high){
        int mid = 0;
        while(low <= high){
            mid = low + (high -low) / 2;
            if(array[mid] == k){
                if(mid > 0 && array[mid - 1] != k || mid == 0)
                    return mid;
                else
                    high = mid - 1;
            }
            else if(array[mid] > k)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
    private int getLastK(int [] array, int k, int low, int high){
        int mid = 0;
        while(low <= high){
            mid = low + (high -low) / 2;
            if(array[mid] == k){
                if(mid < array.length - 1 && array[mid + 1] != k || mid == array.length - 1)
                    return mid;
                else
                    low = mid + 1;
            }
            else if(array[mid] > k)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
}

Runtime：18ms

思路三：

因为data中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索(k-0.5)和(k+0.5)这两个数应该插入的位置，然后相减即可。

需要对二分法的代码进行简单的变形修改。

代码：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0)
            return 0;
        return biSearch(array, k + 0.5) - biSearch(array, k - 0.5);
    }
    private int biSearch(int [] array, double k){
        int low = 0, high = array.length - 1;
        while(low <= high){
            int mid = low + (high -low) / 2;
            if(array[mid] > k)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }
}

Runtime：16ms