剑指Offer[53-1]-在排序数组中查找数字

题目

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

示例:

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

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

python代码

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        cnt = 0
        for i in nums:
            if i==target:
                cnt+=1
            elif i>target:
                break
        return cnt

这道题比较常规,首先数组是一个排序数组,我们要利用这种有序性,因为,target要是存在于这个数组,那么肯定都是连续在一起的。最先想到的方式就是遍历数组,找到第一个target,开始计数,直到当前值不等于target停止。

思考

我们发现这个问题分两步
1. 首先找到target;
2. 对所有target计数。
自然而然,我们可以使用二分查找法解决第一步(时间复杂度降为log(N)),然后以查找到的target为中心,向两边开始计数。

发表评论

电子邮件地址不会被公开。