题目描述：
统计一个数字在排序数组中出现的次数。
分析：
思路一：首先想到的就是用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;
}
}
运行成功
