53 数字在升序数组中出现的次数

牛客

描述

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

由于是排序数组，可以使用二分查找找出 k 的最左位置和最右位置，时间复杂度 o(log n) ，空间复杂度 o(1 )

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array==null || array.length==0) return 0;
        int left=findFirstK(array, k, 0, array.length-1);
        if(left==-1) return 0;
        int right=findLastK(array, k, left, array.length-1);
        return right-left+1;
       
    }
    
    private int findFirstK(int[] array, int k, int begin, int end){
        while(begin<end){
            int mid=(begin+end)/2;
            int t=array[mid];
            if(t>=k){
                end=mid;
            } else {
                begin=mid+1;
            }
        }
        if(array[end]==k) return end;
        return -1;
    }
    
    private int findLastK(int[] array, int k, int begin, int end){
        while(begin<end){
            int mid=(begin+end+1)/2;
            int t=array[mid];
            if(t<=k){
                begin=mid;
            } else {
                end=mid-1;
            }
        }
        if(array[begin]==k) return begin;
        return -1;
    }
}