剑指offer(三十七)-数字在升序数组中出现的次数(Java版)

示例1

输入：[1,2,3,3,3,3,4,5],3

返回值：4

示例2

输入：[1,3,4,5],6

返回值：0

简单暴力，直接循环即可，由于数组是非降序数组，循环的时候，判断当前值是否大于判断值，如果大于的话，终止循环，返回结果即可。代码如下 

public int firstGetNumberOfK(int [] array , int k) {
        int result = 0;
        if(null == array || array.length < 1 || array[array.length-1] < k){
            return result;
        }
        for (int i = 0; i < array.length; i++) {
            if(array[i] == k){
                result++;
            }
            if(k < array[i]){
                break;
            }
        }
        return result;
    }

由于数组是非降序数组，我们可以采用二分法先来确定k在数组里面的位置，当然java本身已经提供了这个方法int i = Arrays.binarySearch(array, k);，然后双向循环，判断即可。代码如下

public int secondGetNumberOfK(int [] array , int k) {
    int result = 0;
    if(null == array || array.length < 1 || array[array.length-1] < k){
        return result;
    }
    //int i = Arrays.binarySearch(array, k);
    int left = 0;
    int right = array.length;
    int index = 0;
    while (left < right){
        int mid = (left + right) / 2;
        if(array[mid] == k){
            index = mid;
            break;
        }
        if(array[mid] > k){
            right = mid-1;
        }else {
            left = mid+1;
        }
    }
    if(index == 0 && array.length == 1){
        if(array[0] == k){
            return 1;
        }
    }
    if(index > 0){
        left = index-1;
        right = index;
        while (left >= 0){
            if(array[left] == k){
                result++;
            }
            if(array[left--] < k){
                break;
            }
        }
        while (right < array.length){
            if(array[right] == k){
                result++;
            }
            if(array[right++] > k){
                break;
            }
        }
    }
    return result;
}