一、题目

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

点击查看原题
难度级别： 简单

二、思路

1）二分法

统计数字在排序数组中出现次数，由于数组是从小到大排序好的，该过程分为两步：

第一步找到数字位置，采用二分法查找更快速 第二步，根据找到数字的位置向两边搜索并统计

三、代码

1）二分法

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int ans = 0;
  4.         int loc = find(nums, target);
  5.         int left = loc - 1;
  6.         while (left >= 0 && nums[left--] == target) {    // 向左搜索
  7.             ans++;
  8.         }
  9.         while (loc < nums.length && nums[loc++] == target) {  // 向右搜索
  10.             ans++;
  11.         }
  12.         return ans;
  13.     }
  14.     private int find(int[] nums, int target) {
  15.         int s = 0, e = nums.length;
  16.         while (s < e) {
  17.             int mid = (s + e) / 2;
  18.             if (nums[mid] == target) {
  19.                 return mid;
  20.             } else if (nums[mid] < target) {
  21.                 s = mid + 1;
  22.             } else {
  23.                 e = mid;
  24.             }
  25.         }
  26.         return s;
  27.     }
  28. }

C为目标数字出现次数，时间复杂度为O(logn+C)，空间复杂度为O(1)