[数据结构与算法]LeetCode:剑指 Offer 53 - I. 在排序数组中查找数字 I————简单

题目

剑指 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

解题思路1

• 直接用Python自带的count函数。

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        return nums.count(target)

运行结果

解题思路2

• 二分法。
• 寻找左边界和右边界，然后计算出现的次数。

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # return nums.count(target)
        # 搜索右边界 right
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] <= target: i = m + 1
            else: j = m - 1
        right = i  # right==
        # 若数组中无 target ，则提前返回
        if j >= 0 and nums[j] != target: return 0
        # 搜索左边界 left
        i = 0
        while i <= j:
            m = (i + j) // 2
            if nums[m] >= target: j = m - 1
            else: i = m + 1
        left = j
        return right - left - 1

运行结果