题目难度: 简单原题链接今天继续更新 Leetcode 的剑指 Offer专项突击版系列, 大家在公众号算法精选里回复剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~题目描述某班级考试成绩按非严格递增顺序记录于整数数组 scores请返回目标成绩 target 的出现次数。示例 1输入: scores [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target 4输出: 3示例 2输入: scores [1, 2, 3, 5, 7, 9], target 6输出: 0提示0 scores.length 105-10^9 scores[i] 109scores 是一个非递减数组-10^9 target 10^9题目思考可以用小于 O(N)的时间复杂度得出结果吗?可以做到 O(1) 空间复杂度吗?解决方案思路一个比较容易想到的思路是使用一个计数字典, 遍历一遍数组统计每个数的出现次数, 最后返回 target 的次数. 但这样时间和空间复杂度都是 O(N), 也用不上题目中数组是排序的这一条件如何利用排序这一条件统计数字出现次数呢? 我们可以尝试二分查找的思路, 分别找到该数字的左右边界对应的下标, 然后次数就是右边界-左边界1(数组存在该数字的情况下)查找左边界: 如果找到等于 target 的数时, 需要继续往左找. 而如果数组中没有等于 target 的数, 则直接返回 None, 此时就知道该数字的出现次数为 0 了, 无需继续找右边界查找右边界: 如果找到等于 target 的数时, 需要继续往右找注意可以将二分查找代码整合到一个方法中, 传入一个 flag 标记当前是找左边界还是右边界, 以减少代码冗余下面代码对必要的步骤有详细的解释, 方便大家理解复杂度时间复杂度 O(logN): 二分查找两次空间复杂度 O(1): 只定义了几个变量代码classSolution:defcountTarget(self,scores:List[int],target:int)-int:defbinarySearch(isleft):# 传入flag isleft, 标记当前是查找左边界还是右边界s,e0,len(scores)-1# 初始化结果为NoneresNonewhilese:m(se)1ifscores[m]target:ifisleft:# 当前查找的是左边界, 更新结果为等于target的更小的下标, 同时向左继续查找resmifresisNoneelsemin(res,m)em-1else:# 当前查找的是右边界, 更新结果为等于target的更大的下标, 同时向右继续查找resmifresisNoneelsemax(res,m)sm1elifscores[m]target:sm1else:em-1returnres leftbinarySearch(True)ifleftisNone:# 如果左边界不存在, 则说明整个数组没有target, 直接返回0return0rightbinarySearch(False)# 最终结果就是右边界-左边界1returnright-left1大家可以在下面这些地方找到我~我的 GitHub我的 Leetcode我的 CSDN我的知乎专栏我的头条号我的牛客网博客我的公众号: 算法精选, 欢迎大家扫码关注~
