剑指 Offer 53 - I. 在排序数组中查找数字 I

题目描述

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

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

限制：

0 <= 数组长度 <= 50000

思路一：

先使用二分法查找数字的下标，如果找到了在这个下标的前后分别计数累加，否则直接返回0

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3         
 4         // 二分法查找数字的下标
 5         int index = binaryFind(nums, target);
 6         int cnt = 0;
 7         // 如果找到了在这个下标的前后分别计数累加
 8         if(index != -1){
 9             cnt = 1;
10             int j = index + 1;  // 分别向左和向右统计与target相等的元素个数
11             int len = nums.length;
12             while(j < len && nums[j] == target){
13                 cnt++;
14                 j++;
15             }
16             j = index - 1;
17             while(j >= 0 && nums[j] == target){
18                 cnt++;
19                 j--;
20             }
21         }
22         return cnt;
23     }
24 
25     public int binaryFind(int[] nums, int target){
26         int left = 0, right = nums.length - 1;
27         int mid = 0;
28         while(left <= right){
29             mid = (left + right) / 2;
30             if(target < nums[mid]){
31                 right = mid - 1;
32             }else if(target > nums[mid]){
33                 left = mid + 1;
34             }else{
35                 return mid;
36             }
37         }
38         return -1;
39     }
40 
41 }

leetcode运行时间为0ms, 空间为42MB

复杂度分析：

时间复杂度：二分查找的时间为O(logn), 第二次往前后查找给定数字的查找次数是不确定的，最坏是O(n),所以时间复杂度为O(n)

空间复杂度：O(1)

思路二：

查找taget在数组的左右边界，左右边界做差即使出现的次数

 

思路三：

对思路二的改进