题解 | #数字在升序数组中出现的次数#

题目描述

统计一个数字在升序数组中出现的次数。
示例1
输入：[1,2,3,3,3,3,4,5],3
返回值：4

题目分析

在一个数组中统计一个数字的出现次数，首先可以直接遍历这个数组，使用一个变量count来记录数字出现的次数，碰到与目标数字相同的，则次数加1。
因为数组是升序的（有序即可），所以可以使用二分查找来提高速度。

解题思路

方法1：暴力法
遍历数组的过程中，考虑到数组是升序的，对于比目标数字大的部分直接跳过，节省时间。

方法2：二分法
二分法的统一模板为：

while(left<=right){
   int mid = (left+right)/2;
   if(nums[mid]==target) return mid;
   if(nums[mid]>target) right=mid-1;
   if(nums[mid]<target) left=mid+1;
}

在查找某个数字的场景时，使用二分***在nums[mid] == target时，直接返回中间的下标值。
而需要统计数字出现的次数时，不能直接返回，而是继续二分查找，直到找到数字的左下界或右上界。

代码实现

方法1：暴力法

public int GetNumberOfK(int [] array , int k) {
       // 记录出现的次数
       int count = 0;
       for(int i=0;i<array.length;i++){
            // 相等次数加1
           if(array[i] == k){
               count++;
           }else if(array[i] > k){
                // 数组有序，一旦比目标值大，直接退出
               break;
           }
       }
        return count;
    }

时间复杂度：O(n)，计算次数最多需要遍历整个数组，时间复杂度为数组长度n；
空间复杂度：O(1)，只需要常量个数的变量即可。

方法2：二分法

public int GetNumberOfK(int [] array , int k) {
       int left = 0;
       int right = array.length;
       int l = 0;
       int r = 0;
        // 第一次二分查找
       while(left<right){
           int mid = left + (right-left)/2;
          if(array[mid] < k){
              // 确定左下界
               left = mid+1;
           }else{
               right = mid;
           }
        }
        // 左下界坐标
        l = left;
        left = 0;
        right = array.length;
        // 第二次二分查找
        while(left<right){
           int mid = left + (right-left)/2;
          if(array[mid] <= k){
              // 确定右上界
               left = mid+1;
           }else{
               right = mid;
           }
        }
        // 右上界坐标
        r = left;
        // 中间为目标数字相同的个数
        return r-l;
    }

时间复杂度：O(logn)，使用了两次二分查找，时间花费最多为 2*logn；
空间复杂度：O(1)，只需要常量个数的变量即可。