给定一个长度为 n 的数组 a,数组中的每个元素都是正整数。我们需要回答 n 个查询,第 i 个查询是关于数组前缀 ai,a2,...,ai 的:
对于每一个查询 i,请你计算在前缀 ai,a2,...,ai 中数字 i 出现了多少次。
第一行包含一个整数 n (1≤n≤105),表示数组的长度。
第二行包含 n 个正整数 a1,a2,…,an (1≤ai≤n),表示数组 a。
输出 n 个整数,第 i 个整数表示数字 i 在前缀 ai,a2,...,ai 中出现的次数。
输入
5
1 2 1 3 2
输出
1 1 0 0 0
前缀 [1] 中,数字 1 出现 1 次。
前缀 [1, 2] 中,数字 2 出现 1 次。
前缀 [1, 2, 1] 中,数字 3 出现 0 次。
前缀 [1, 2, 1, 3] 中,数字 4 出现 0 次。
前缀 [1, 2, 1, 3, 2] 中,数字 5 出现 0 次。
本题要求我们对一个数组执行多个查询,每个查询询问数组前缀中某个数字出现的次数。那我们可以利用一个哈希表就可以了,哈希表的使用,哈希1也是详细提到过了,此处省略...... 哈希表相关介绍
给定一个长度为 n 的数组 a,数组中的每个元素都是正整数,且满足 1≤ai≤n。我们需要回答 n 个查询,第 i 个查询是关于数组前缀 a1,a2,…,ai 中数字 i 出现的次数。
为了高效地回答每个查询,我们需要在遍历数组的同时,记录每个数字的出现次数。由于查询的数字与其位置 i 对应,即第 i 个查询是询问数字 i 在前缀 a1 到 ai 中出现的次数,因此我们可以通过以下步骤解决问题:
使用哈希表记录出现次数:
利用字典(dict
)来记录每个数字在数组中出现的次数。遍历数组时,对于每个元素 (a[i]),将其出现次数加1。
示例代码:
counts[num] += 1 # 更新数字 num 的出现次数
实时输出查询结果: 对于每个 (i),直接查询数字 (i) 在当前前缀中的出现次数,并输出。
示例代码:
print(counts[i], end=" ") # 输出数字 i 在前缀中出现的次数
假设我们有一个数组 a = [2, 1, 3, 2, 1]
,我们需要回答每个查询:数字 i
在数组前缀 [a_1, a_2, ..., a_i]
中出现的次数。
counts
是空的。a[1] = 2
,哈希表更新为 {2: 1}
,此时数字 1
在前缀 [2]
中出现了 0
次,输出 0
。a[2] = 1
,哈希表更新为 {2: 1, 1: 1}
,此时数字 2
在前缀 [2, 1]
中出现了 1
次,输出 1
。a[3] = 3
,哈希表更新为 {2: 1, 1: 1, 3: 1}
,此时数字 3
在前缀 [2, 1, 3]
中出现了 1
次,输出 1
。a[4] = 2
,哈希表更新为 {2: 2, 1: 1, 3: 1}
,此时数字 4
在前缀 [2, 1, 3, 2]
中出现了 0
次,输出 0
。a[5] = 1
,哈希表更新为 {2: 2, 1: 2, 3: 1}
,此时数字 5
在前缀 [2, 1, 3, 2, 1]
中出现了 0
次,输出 0
。所以,最终输出的结果是:0 1 1 0 0
。
# 输入处理
n = int(input()) # 数组长度
a = list(map(int, input().split())) # 数组元素
# 初始化一个字典,记录数字出现的次数
counts = {i: 0 for i in range(1, n + 1)}
# 遍历数组,计算每个数字在前缀中的出现次数
for i in range(n):
num = a[i]
counts[num] += 1 # 更新数字 num 的出现次数
# 输出数字 i+1 在前缀 [a1, a2, ..., ai] 中的出现次数
if i > 0:
print(' ', end='')
print(counts[i + 1], end='')
print() # 输出换行