剑指offer_数字在排序数组中出现的次数

问题

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

例子

思路

• 方法1

  O(n)

• 方法2

  O(logn) 二分

代码

//方法1 O(n)
    public int GetNumberOfK(int [] array , int k) {
        int res=0;
        for(int n: array) {
            if(n==k) res++;
            if(n!=k && res>=1) break;
        }
        return res;
       
    }
//方法2 O(logn)
public int GetNumberOfK(int [] array , int k) {
        int index = Arrays.binarySearch(array, k);
        if(index<0) return 0;
        int res = 1;
        for(int i=index-1; i>=0; i--) {
            if(array[i]==k) res++;
            else break;
        }
        for(int i=index+1; i<array.length; i++) {
            if(array[i]==k) res++;
            else break;
        }
        
        return res;
       
    }