题目链接

题目描述

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

解题思路

  1. 利用二分查找，找到任意一个 k
  2. 由于 k 有多个，并且 当前找到的 k 可能在任意位置 。所以， 在当前 k 的前后进行遍历查找

示例

  1. 输入：
  2. {1,2,3,3,3,3,4,5}  3
  4. 输出：
  5. 4

代码

  1. public int GetNumberOfK(int [] array , int k) {
  2.         if (array == null || array.length == 0) {
  3.             return 0;
  4.         }
  6.         //二分查找
  7.         int start = 0, end = array.length - 1;
  8.         int t = -1;
  9.         while (start <= end) {
  10.             int mid = (start + end) / 2;
  11.             if (array[mid] == k) {
  12.                 t = mid;
  13.                 break;
  14.             } else if (array[mid] > k) {
  15.                 end = mid - 1;
  16.             } else {
  17.                 start = mid + 1;
  18.             }
  19.         }
  21.         // 如果查找的数字不在数组中
  22.         if (t == -1) {
  23.             return 0;
  24.         }
  26.         // 此时通过二分查找已经找到了其实一个
  27.         // sum用来统计总共的个数，是最后返回的值
  28.         int sum = 0;
  30.         //左侧
  31.         // t 保存的为已经找到数组的索引
  32.         int a = t;
  33.         while (a >= 0 && array[a] == k) {
  34.             sum++;
  35.             a--;
  36.         }
  38.         //右侧
  39.         a = t + 1;
  40.         while (a < array.length && array[a] == k) {
  41.             sum++;
  42.             a++;
  43.         }
  45.         return sum;
  46.     }

补充

二分查找