剑指offer37 数字在升序数组中出现的次数

剑指offer

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

题目描述

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

输入：

[1,2,3,3,3,3,4,5],3

输出：

4

代码

public class Solution {
    public int GetNumberOfK(int [] array , int k) {

        /** solution 1
        if(array==null || array.length==0)return 0;
        int left = 0;
        int right = array.length - 1;
        while(array[left]<k && left<array.length - 1){
            left++;
        }
        while(array[right]>k && right>0){
            right--;
        }

        if(left==right && array[right]==k) return 1;
        if(left>=array.length-1 || right<=0) return 0;
        return right-left+1;
        **/

        // solution 2
        if(array.length <= 0 || array == null) return 0;
        int first = binarySearch(array, k);    //获取起始k的索引
        int last = binarySearch(array, k+1);    //获取末尾k的索引
        return (first == array.length || array[first] != k)? 0 : last - first;
    }

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