題目描述：

統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

分析：

思路一：首先想到的就是用hashmap存儲數(shù)組中的各種元素和其出現(xiàn)的次數(shù)。
時間復雜度O(N)，空間復雜度O(N)

思路二：
但是，題目給出的排序數(shù)組，思路一的方法即使不是排序數(shù)組也可以使用，針對已排序數(shù)組，肯定有更好的方式來簡化計算。
我們考慮，在已經排序的數(shù)組中，某個數(shù)字一定成堆的出現(xiàn)，只要計算這一堆的長度就可以知道該數(shù)字出現(xiàn)的次數(shù)。
同時，對于已經排序的數(shù)組，我們考慮用二分查找的方式來查找這個數(shù)字出現(xià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;
    }
}

運行成功

思路二：二分查找
利用二分查找找到一個數(shù)值可能在該數(shù)組中的第一個最合適的位置，然后判斷該位置上元素是否是是該元素，如果不是，說明這個數(shù)組中不存在這一元素，返回0即可。如果該位置上為該元素，那么這個位置就是該元素在數(shù)組中存在的第一個位置，同理可求出k+1的合適位置（k+1可能存在，也可能不存在于這個數(shù)組中），兩個位置只差即為k出現(xiàn)的次數(shù)。

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;
    }

    /*二分查找算法 --  輸入數(shù)組中該數(shù)值的第一個位置*/
    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;
    }
}

運行成功