| 题目链接 | 2080. 区间内查询数字的频率 |
|---|---|
| 思路 | 二分法（upper_bound - lower_bound） |
| 题解链接 | 简洁写法：统计位置+二分查找（Python/Java/C++/Go/JS/Rust） |
| 关键点 | 预先处理得到每个值所处位置的列表 |
| 时间复杂度 | \(O(n + m \log n)\) |
| 空间复杂度 | \(O(n)\) |
代码实现：
class RangeFreqQuery:
def __init__(self, arr: List[int]):
positions = defaultdict(list)
for i, v in enumerate(arr):
positions[v].append(i)
self.positions = positions
def query(self, L: int, R: int, value: int) -> int:
positions = self.positions[value]
n = len(positions)
def upper_bound():
left, right = -1, n
while left + 1 < right:
mid = (left+right) // 2
if positions[mid] > R:
right = mid
else:
left = mid
return right
def lower_bound():
left, right = -1, n
while left + 1 < right:
mid = (left+right) // 2
if positions[mid] < L:
left = mid
else:
right = mid
return right
return upper_bound() - lower_bound()
Python-官方库
class RangeFreqQuery:
def __init__(self, arr: List[int]):
positions = defaultdict(list)
for i, v in enumerate(arr):
positions[v].append(i)
self.positions = positions
def query(self, L: int, R: int, value: int) -> int:
positions = self.positions[value]
return bisect_right(positions, R) - bisect_left(positions, L)