难度: Easy
某班级考试成绩按非严格递增顺序记录于整数数组 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-109 <= scores[i] <= 109scores 是一个非递减数组-109 <= target <= 109注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
运行时间: 32 ms
内存: 15.6 MB
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
return self.left_bound(nums, target+1) - self.left_bound(nums, target)
def right_bound(self, nums, target):
lo = 0
hi = len(nums)-1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] > target:
hi = mid - 1
elif nums[mid] < target:
lo = mid + 1
elif nums[mid] == target:
lo = mid + 1
return lo
def left_bound(self, nums, target):
lo = 0
hi = len(nums)-1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] > target:
hi = mid - 1
elif nums[mid] < target:
lo = mid + 1
elif nums[mid] == target:
hi = mid - 1
return hi
题解使用二分查找算法来找到目标成绩的左右边界索引。首先，left_bound函数寻找target应该插入的位置，即第一次出现的位置。right_bound函数则找到target+1应该插入的位置，即target最后一次出现的位置的后一位。通过计算right_bound(target+1) - left_bound(target)得到target的出现次数。如果target在数组中不存在，这两个函数返回的值将相同，因此结果为0。
时间复杂度: O(log n)
空间复杂度: O(1)
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 使用left_bound函数找到target和target+1的左边界，计算两者之差得到target的出现次数
return self.left_bound(nums, target+1) - self.left_bound(nums, target)
def right_bound(self, nums, target):
# 初始化左右指针
lo = 0
hi = len(nums)-1
# 二分查找
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] > target:
hi = mid - 1
elif nums[mid] < target:
lo = mid + 1
elif nums[mid] == target:
lo = mid + 1
# 返回左边界
return lo
def left_bound(self, nums, target):
# 初始化左右指针
lo = 0
hi = len(nums)-1
# 二分查找
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] > target:
hi = mid - 1
elif nums[mid] < target:
lo = mid + 1
elif nums[mid] == target:
hi = mid - 1
# 返回右边界
return hi
在left_bound函数中，当nums[mid]等于target时移动hi指针是为了继续在数组的左侧部分寻找可能存在的target的更前位置，确保找到target的第一个出现位置。相反，在right_bound函数中，当nums[mid]等于target时移动lo指针是为了寻找数组中target的最后一个位置的右侧，即继续探索数组右侧以确认target最后一次出现的位置。这样的处理确保了能精准找到target的边界，从而正确统计其出现次数。
right_bound函数通过寻找target+1的左边界来间接确定target的右边界。在大多数情况下，这种方法是有效的，包括当target是数组中的最大值时。如果target是数组中的最大值，则target+1不会在数组中出现，因此right_bound函数将返回数组长度（nums.length），这正是target最后出现位置的下一位置，从而正确地计算出target的出现次数。
如果数组为空，那么left_bound和right_bound函数都会返回初始化的边界值（left_bound返回-1，right_bound返回0），从而计算得到的target的数量为0-(-1)=1，这显然是不正确的，应该特别处理数组为空的情况。如果target小于数组中的最小值或大于最大值，left_bound将返回-1，right_bound将返回0或数组长度，计算结果将正确显示target出现次数为0。
在二分查找中，最终返回hi或lo而不是mid是因为hi和lo指针最终将指向target应该插入的位置。在left_bound中，返回hi是因为循环结束时，hi指向target应该插入的最后一个有效位置的左侧，即第一个小于target的位置。在right_bound中，返回lo是因为循环结束时，lo指向第一个大于target的位置，即target+1应该插入的位置。这样的设计使得算法能够正确处理包括边界在内的各种复杂情况。