数字在排序数组中出现的次数（java）

题目描述：

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

分析：

思路一：首先想到的就是用hashmap存储数组中的各种元素和其出现的次数。
时间复杂度O(N)，空间复杂度O(N)

思路二：
但是，题目给出的排序数组，思路一的方法即使不是排序数组也可以使用，针对已排序数组，肯定有更好的方式来简化计算。
我们考虑，在已经排序的数组中，某个数字一定成堆的出现，只要计算这一堆的长度就可以知道该数字出现的次数。
同时，对于已经排序的数组，我们考虑用二分查找的方式来查找这个数字出现的位置。

解答：

思路一：hashmap

import java.util.HashMap;
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if (array == null || array.length == 0) return 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int result = 0;
        for(int i=0;i<array.length;i++) {
            int a = array[i];
            if (map.containsKey(a)) {
                map.put(a, map.get(a) + 1);
            }else{
                map.put(a, 1);
            }
        }
        if (map.get(k) != null) {
            result = map.get(k);
        }
        return result;
    }
}

运行成功

---

思路二：二分查找
利用二分查找找到一个数值可能在该数组中的第一个最合适的位置，然后判断该位置上元素是否是是该元素，如果不是，说明这个数组中不存在这一元素，返回0即可。如果该位置上为该元素，那么这个位置就是该元素在数组中存在的第一个位置，同理可求出k+1的合适位置（k+1可能存在，也可能不存在于这个数组中），两个位置只差即为k出现的次数。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if (array == null || array.length == 0) return 0;
        if (k < array[0]) return 0;
        int first = binarySearch(array, k);
        int last = binarySearch(array,k+1);
        return (first==array.length || array[first]!=k)?0:last-first;
    }

    /*二分查找算法 --  输入数组中该数值的第一个位置*/
    public static int binarySearch(int[] nums, int k) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

运行成功