看到题目要求输出,目前i这个数的前缀出现了多少次,那我们可以利用一个哈希表就可以了,哈希表的使用,哈希1也是详细提到过了,此处省略...... 哈希表相关介绍
给定一个长度为 n 的数组 a,数组中的每个元素都是正整数。我们需要回答 n 个查询,第 i 个查询是关于数组前缀 a1,a2,...,ai 的:
对于每一个查询 i,请你计算在前缀 a1,a2,...,ai 中数字 i 出现了多少次。
第一行包含一个整数 n (1≤n≤105),表示数组的长度。
第二行包含 n 个正整数 a1,a2,…,an (1≤ai≤n),表示数组 a。
输出 n 个整数,第 i 个整数表示数字 i 在前缀 a1,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 次。