剑指 Offer 53 – I. 在排序数组中查找数字 I

题目描述

https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
统计一个数字在排序数组中出现的次数。

示例 1:

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

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

限制：

0 <= 数组长度 <= 50000

解题思路

使用二分法查找。先复习一下二分法：

def BinarySearcher(nums: list[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        while low <= high:  # 注意是<=,不然没法处理high==low的情况
            mid = int((low + high) / 2)
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                high = mid - 1
            elif nums[mid] < target:
                low = mid + 1
        return -1  # 找不到

一种可行的做法就是在二分法找到target的位置之后，再分别向两边扩展，看看周边有没有和target相同的数目，最终输出总数目。

解题代码

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = int((low + high) / 2)
            if nums[mid] == target:
                count = 1
                i, j = mid - 1, mid + 1
                # 这里while两个条件是为了防止数组越界
                while j < len(nums) and nums[j] == target:
                    count += 1
                    j += 1
                while i >= 0 and nums[i] == target:
                    count += 1
                    i -= 1
                return count
            elif nums[mid] > target:
                high = mid - 1
            elif nums[mid] < target:
                low = mid + 1
        return 0

执行结果

执行结果：通过
执行用时：40 ms, 在所有 Python3 提交中击败了73.60%的用户
内存消耗：15.9 MB, 在所有 Python3 提交中击败了5.04%的用户