题目来源 剑指offer

01 题目描述

给一个排序数组 如 {1,2,3,4,5,5,6,7,8,9}. 统计一个"数字"在排序数组中出现的次数。如数字1，出现1次，数字5输出5次。

02 解法1

遍历数组，对比数组的值和 "数字"，边遍历，边统计,最终得到结果。时间复杂度是O(n)

03 解法2

因为是排序数组，所以我们是否可以利用二分查找法，去确定这个数在数组中出现的最左边的位置start，和最右边的位置end，然后end-start+1。即为出现的次数。

获取num最左边的位置，

循环开始。

取mid = ( start + end ) >> 1;如果 arr[mid] < num:

说明num在mid的右面，start = mid + 1；

如果 arr[mid] > num;

说明num在mid的左面，end = mid - 1；

如果 arr[mid] == num;

首先判断mid是否已经是边界，(1) mid==start？。 如果相等直接返回start。不等继续判断

arr[mid - 1] < num?? 。小于num，说明mid是边界，直接返回mid，否则继续。

end = mid - 1；(因为要找最左边的，所以要往左边缩小范围。)

继续循环

获取num最大的数值位置，大体类似。

因用二分查找实现，时间复杂度 O(logn)

04 代码

public static int getRepeatCountInArray(int[] result, int num) { if (result == null || result.length == 0) { return 0; } int left = findLeft(result, 0, result.length - 1, num); int right = findRight(result, 0, result.length - 1, num); if (left > -1 && right > -1) { return right - left + 1; } return 0;}public static int findLeft(int[] result, int start, int end, int num) { while (start <= end) { int mid = (start + end) >> 1; if (result[mid] == num) { if (mid == start || (mid - 1 >= start && result[mid - 1] < num)) { return mid; } end = mid - 1; } else if (result[mid] < num) { start = mid + 1; } else { end = mid - 1; } } return -1;}public static int findRight(int[] result, int start, int end, int num) { while (start <= end) { int mid = (start + end) >> 1; if (result[mid] == num) { if (mid == end || (mid + 1 <= end && result[mid + 1] > num)) { return mid; } start = mid + 1; } else if (result[mid] < num) { start = mid + 1; } else { end = mid - 1; } } return -1;}

测试用例

public static void main(String[] args) { int[] result = new int[]{1,2,3,3,3,3,3,5,6}; System.out.println(getRepeatCountInArray(result, 3)); System.out.println(getRepeatCountInArray(result, 1));// System.out.println(getRepeatCountInArray(result, 5));// System.out.println(getRepeatCountInArray(result, 7)); }