每日一题：剑指 Offer 53 - I. 在排序数组中查找数字 I-爱代码爱编程

每日一题：剑指 Offer 53 - I. 在排序数组中查找数字 I

1、题目

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

示例 1:

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

示例 2:

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

限制：

0 <= 数组长度 <= 50000

2、解法

题目比较清晰，最简单暴力的方法是从左到右进行进行判断统计，时间复杂度为O(n)，但是我们确忽略了数组是排序好的特点（这里为升序）。

对于排序好的数组，查找相关的操作很容易想到二分法，所以我们用二分法来实现，这样时间复杂度降为O(nlogn)，最坏情况下为O(n)，即数组所有元素都一样。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        length = len(nums)
        if length == 0:
            return 0

        result = 0
        left, right = 0, length-1
        while (left<=right):
            mid = int((left+right)/2)
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid]==target: # 说明找到了匹配的值，后续的匹配只需要在这个位置前后进行查找就可以了
                result += 1
                
                tmpMid = mid-1
                while tmpMid>=left:
                    if nums[tmpMid]==target:
                        result += 1
                        tmpMid -= 1
                    else:
                        break
                
                tmpMid = mid + 1
                while tmpMid<=right:
                    if nums[tmpMid]==target:
                        result += 1
                        tmpMid += 1
                    else:
                        break
                return result  # 注意这里返回结果，没必要继续查找了
        return result

执行用时：40 ms, 在所有 Python3 提交中击败了72.93%的用户
内存消耗：15.6 MB, 在所有 Python3 提交中击败了20.20%的用户