题目描述
统计一个数字在排序数组中出现的次数。
算法解析：
最直观的解法，就是从头到尾扫描整个排序数组，但是对于排序数组的话，如果我们使用二分法的话，应该会起到意想不到的结果，但是既然是有多个相同的数字，那么我们可以利用二分法查找第一个k和最后一个k，然后就可以找出出现的次数。
代码如下：
public int GetNumberOfK(int [] array , int k) { int number = 0; if (array != null && array.length > 0){ int firstK = getFirstK(array, k, 0, array.length - 1); int lastK = getLastK(array, k, 0, array.length - 1); if (firstK > -1 && lastK > -1){ number = lastK - firstK + 1; } } return number; } PRivate int getLastK(int[] array, int k, int start, int end) { if (start > end){ return -1; } int mid = (start + end) >> 1; if (array[mid] == k){ if ((mid < array.length - 1 && array[mid + 1] != k) || mid == array.length - 1){ return mid; }else { start = mid + 1; } }else if (array[mid] < k){ start = mid + 1; }else{ end = mid - 1; } return getLastK(array, k, start, end); } private int getFirstK(int[] array, int k, int start, int end) { if (start > end){ return -1; } int mid = (start + end) >> 1; if (array[mid] == k){ if ((mid > 0 && array[mid - 1] != k) || mid == 0){ return mid; }else { end = mid - 1; } }else if (array[mid] > k){ end = mid - 1; }else{ start = mid + 1; } return getFirstK(array, k, start, end); }新闻热点
疑难解答
