题目描述

给定一个长度为 $n$ 的数组 $a$ 和 $Q$ 个询问。每个询问包含一个数 $x$ 和一个整数 $k$。对于每个询问，求数 $x$ 在数组中第 $k$ 次出现的位置（位置从 $1$ 开始）。如果 $x$ 在数组中出现次数不足 $k$ 次，则输出 $-1$。

输入描述

第一行包含两个整数 $n$ 和 $Q$，分别表示数组的长度和询问的数量， $1 \leq n, Q \leq 10^5$。

第二行包含 $n$ 个整数，表示数组$a$，每个元素满足 $1 \leq$ $a_i$ $\leq 10^9$。

接下来的 $Q$ 行，每行包含两个整数 $x$ 和 $k$，表示一个询问，其中 $1 \leq x \leq 10^9$，$1 \leq k \leq n$。

输出描述

对于每个询问，输出一个整数，表示 $x$ 在数组中第 $k$ 次出现的位置。如果 $x$ 的出现次数不足 $k$ 次，输出 $-1$。

样例

输入

8 5
1 2 3 2 1 2 3 2
2 1
2 2
3 1
3 2
4 1

输出

2
4
3
7
-1

样例说明

在样例中，数组为 [1, 2, 3, 2, 1, 2, 3, 2]。

第一个询问是找数 2 的第 1 次出现，位置为 2。

第二个询问是找数 2 的第 2 次出现，位置为 4。

第三个询问是找数 3 的第 1 次出现，位置为 3。

第四个询问是找数 3 的第 2 次出现，位置为 7。

第五个询问是找数 4 的第 1 次出现，数组中没有 4，所以输出 -1。

【哈希2】塔子哥的口袋2

前言

• Python中容器的嵌套使用

在Python中，容器的嵌套使用也是常见的做法。容器的嵌套是指将一个容器存储在另一个容器中，例如：

常见的Python容器嵌套

1. 列表嵌套（list[list[T]]） 用于表示二维数组或矩阵。 例如：

   matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
   

   Copy

2. 字典与列表的组合（dict[int, list[int]]） 用于表示一个键值对，其中键是整数，值是一个整数列表。 例如：

   graph = {1: [2, 3], 2: [4], 3: [5]}
   

   Copy

3. 集合嵌套（set[frozenset] 或 set[list]） 用于存储唯一的容器元素集合，避免重复项。 例如：

   unique_sets = {frozenset([1, 2]), frozenset([3, 4])}
   

   Copy

4. 多级嵌套字典（dict[int, dict[int, list[int]]]） 用于表示一个嵌套字典结构，其中每个键对应另一个字典或列表。 例如：

   nested_map = {1: {2: [3, 4], 3: [5, 6]}, 2: {1: [7, 8]}}
   

   Copy

我们可以很自然的想到用一个二维数组做完这个题目，对于目前题目而言呢，由于其元素值可以达到 $10^9$，开不了这么大的二维数组，我们可以选择上面第二种容器的嵌套（defaultdict(list)）。

因此我们需要知道 defaultdict 和 list 的使用方法，然后我们可以尝试解决这个题目了。

Python的defaultdict

defaultdict 是 Python 中 collections 模块提供的一个字典类，它与普通字典的区别在于：当访问一个不存在的键时，defaultdict 会自动为该键创建一个默认值，而不是抛出 KeyError 异常。

主要特点：

1. 默认值工厂函数： 当你创建 defaultdict 时，必须指定一个工厂函数（也可以理解为一个默认值生成规则）。这个工厂函数会在访问一个不存在的键时被调用，生成并返回一个默认值。

2. 避免 KeyError： 对于普通字典，如果访问一个不存在的键，会抛出 KeyError 异常；而在 defaultdict 中，访问不存在的键时会自动调用工厂函数生成并返回一个默认值。

常见的默认值工厂函数：

• int: 默认值是 0
• list: 默认值是空列表 []
• set: 默认值是空集合 set()
• str: 默认值是空字符串 ""

基本操作：

1. 变量声明与初始化

from collections import defaultdict

positions = defaultdict(list)

2. 插入元素

from collections import defaultdict

def main():
    positions = defaultdict(list)
    
    # 示例数据
    a = [1, 2, 3, 2, 1, 2, 3, 2]
    
    # 遍历数组，记录每个数字出现的位置（从1开始计数）
    for i in range(len(a)):
        positions[a[i]].append(i + 1)
    
    # 输出 positions
    for key, value in positions.items():
        print(f"数字 {key} 出现的位置: {' '.join(map(str, value))}")

if __name__ == "__main__":
    main()

也可以像二维数组一样访问下标，类似于下面题解：

positions[x][k - 1]

题解

题面分析

本题要求在一个长度为 $n$ 的数组中，回答 $Q$ 个查询。每个查询包含两个整数 $x$ 和 $k$，要求找出数字 $x$ 在数组中第 $k$ 次出现的位置（位置从 $1$ 开始）。如果 $x$ 在数组中出现次数不足 $k$ 次，则输出 $-1$。

由于数组长度 $n$ 和查询数量 $Q$ 均可达 $10^5$，需要高效的预处理方法以便快速回答每个查询。

思路分析

1. 数据预处理：

遍历数组中的每个元素，将其值作为键，位置（从 $1$ 开始）作为值存储在哈希表中。由于数字的范围较大（$1 \leq a_i \leq 10^9$），使用 defaultdict 来实现哈希表，可以高效地存储和查找数据。

from collections import defaultdict

positions = defaultdict(list)

for i in range(n):
    x = a[i]
    positions[x].append(i + 1)  # 存储的是位置，位置从1开始

将 a[i] 输入成功后，下一行代码将当前元素 a[i] 的位置（从 1 开始）添加到哈希表 positions 中对应数字的列表里，以记录该数字在数组中的所有出现位置。

2. 查询处理：

for _ in range(Q):
    x, k = map(int, input().split())
    
    # 如果 x 在数组中出现的次数少于 k 次，返回 -1
    if len(positions[x]) < k:
        print(-1)
    else:
        # 返回 x 的第 k 次出现的位置
        print(positions[x][k - 1])

对于每个查询 $(x, k)$，检查 $x$ 的出现次数是否至少为 $k$。如果是，输出 $x$ 在数组中第 $k$ 次出现的位置，即存储在列表中的第 $k-1$ 个元素。否则，输出 $-1$。

实现细节

选择合适的数据结构：

使用 defaultdict(list) 来存储每个数字及其所有出现的位置。
这种结构允许我们在常数时间内访问特定数字的所有位置，并通过索引快速获取第 $k$ 次出现的位置。

时间复杂度分析：

• 预处理阶段：遍历数组一次，时间复杂度为 $O(n)$。
• 查询阶段：每个查询的处理时间为 $O(1)$，总查询时间为 $O(Q)$。

总体时间复杂度：$O(n + Q)$，符合题目要求。

完整代码

from collections import defaultdict

def main():
    # 输入数组大小 n 和查询次数 Q
    n, Q = map(int, input().split())
    
    # 输入数组
    a = list(map(int, input().split()))
    
    # 预处理：记录每个数的位置
    positions = defaultdict(list)
    for i in range(n):
        positions[a[i]].append(i + 1)  # 存储的是位置，位置从1开始
    
    # 处理每个查询
    for _ in range(Q):
        x, k = map(int, input().split())
        
        # 如果 x 在数组中出现的次数少于 k 次，返回 -1
        if len(positions[x]) < k:
            print(-1)
        else:
            # 返回 x 的第 k 次出现的位置
            print(positions[x][k - 1])

if __name__ == "__main__":
    main()