描述

题目描述

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

示例

输入：[1,2,3,3,3,3,4,5],3
返回值：4

引言

看到有序数组，就要立马想到用二分查找，一般都能解决问题并且优化时间复杂度

知识点：数组，二分法
难度：⭐⭐

题解

解题思路

二分查找法，获取目标值的前后下标，即获取目标值在数组中的长度

关键是运用微妙的 + 0.5 和 - 0.5，找出数组中第一个大于k和最后一个小于k的数的下标，相减就可以获得k在数组中的长度

方法一：二分法

图解

算法流程：

• 二分查找法，返回 num 在 arr 的第一个下标
• 如果找不到目标值，则返回第一个大于目标值的数的下标
• 通过浮点数，只需要找出数组中第一个大于k和最后一个小于k的数的下标，相减就可以获得k在数组中的长度

Java 版本代码如下：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        // 通过浮点数，只需要找出数组中第一个大于k和最后一个小于k的数的下标
        // 相减就可以获得k在数组中的长度
        return helper(array, k + 0.5) - helper(array, k - 0.5);
    }

    // 找到num在arr的第一个下标
    int helper(int[] arr, double num) {
        // 二分法
        int lo = 0, hi = arr.length - 1;
        int mid = 0;
        // 该二分查找法，返回num在arr的第一个下标
        // 如果找不到目标值，则返回第一个大于目标值的数的下标
        while(lo <= hi) {
            // 这种写法可以避免整型相加时溢出
            mid = lo + ((hi - lo) >> 1);
            if(arr[mid] < num) {
                lo = mid + 1;
            } else if(arr[mid] > num) {
                hi = mid - 1;
            }
        }
        // 找到num在arr的第一个下标
        // 如果找不到目标值，则返回第一个大于目标值的数的下标
        return lo; 
    }
}

Python 版本代码如下：

class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        n = len(data)
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if data[mid] < k:
                left = mid + 1
            elif data[mid] > k:
                right = mid - 1
            else:
                right = mid - 1
        l = right
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if data[mid] < k:
                left = mid + 1
            elif data[mid] > k:
                right = mid - 1
            else:
                left = mid + 1
        r = left
        cur = r - l - 1
        return cur if cur > 0 else 0

复杂度分析：

时间复杂度 O(logN)：二分法通常时间复杂度都是O(logN)
空间复杂度 O(1)：只用到整数型的数据类型，常数项级别

总结：求解升序数组的题目一般都可以用二分法解决

方法二：暴力解法

算法流程：

• 遍历、计数即可

Java 版本代码如下：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int count = 0;
        for(int a : array){
            if(k == a){
                count++;
            } 
        }
        return count;
    }
}

Python 版本代码如下：

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if not data:
            return 0
        return data.count(k)

复杂度分析：

时间复杂度 O(N)：遍历数组，长度为 N
空间复杂度 O(1)：只用到整型类型