题目描述

塔子哥有一个包含 $n$ 个整数的口袋。现在，他有 $Q$ 个问题，每个问题询问某个特定的数字在口袋中出现了多少次。请帮助塔子哥回答这些问题。

输入描述

第一行包含两个整数 $n$ 和 $Q$，分别表示口袋中数字的数量和问题的数量，其中 $1 \leq n, Q \leq 10^5$。

第二行包含 $n$ 个整数，表示口袋中的数字，每个数字 $c$ 满足 $-10^9 \leq c \leq 10^9$。

接下来的 $Q$ 行，每行包含一个整数，表示要查询的数字，每个查询数字 $x$ 满足 $-10^9 \leq x \leq 10^9$。

输出描述

对于每个查询，输出一个整数，表示该数字在口袋中出现的次数。

样例

输入

5 3
1 2 2 3 2
2
3
4

输出

3
1
0

样例说明

在样例中，口袋中的数字是 $[1, 2, 2, 3, 2]$。

数字 $2$ 出现了 $3$ 次。

数字 $3$ 出现了 $1$ 次。

数字 $4$ 没有出现过。

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

前言

• 哈希表简介
• Python的哈希表（dict ,Counter）
• 时间复杂度计算

哈希表（Hash Table）

哈希表是一种基于哈希函数（Hash Function）的数据结构，用于实现键值对的快速存储和查找。它的主要特点是：

1.快速查找：平均情况下，哈希表的查找、插入和删除操作的时间复杂度都是 O(1)。

2.键值对存储：哈希表存储的是键值对，每个键（Key）唯一对应一个值（Value）。

3.哈希函数：通过哈希函数将键映射到哈希表中的位置，从而实现快速存取。

在 Python 中，dict 是内置的哈希表实现，它可以用于存储键值对，并提供快速的查找、插入和删除操作。dict 的内部实现使得查找和插入操作的平均时间复杂度为 O(1)，因此它非常适合用于实现哈希表的功能。

Python 中的 dict

dict 是 Python 的一个核心数据结构，允许你通过键（key）来访问对应的值（value）。它的基本操作包括插入、查询、更新和删除，所有这些操作的平均时间复杂度通常是 O(1)。

创建和使用 dict

1. 创建一个 dict： 你可以通过 {} 或 dict() 来创建一个空的字典，或者通过键值对初始化。

   my_dict = dict()  # 创建一个空字典
   my_dict = {"apple": 1, "banana": 2}  # 创建一个带有初始键值对的字典
   

   Copy

2. 插入元素： 通过键来访问字典，并赋值给该键。

   my_dict["orange"] = 3  # 插入一个新的键值对
   print(my_dict)  # 输出：{'apple': 1, 'banana': 2, 'orange': 3}
   

   Copy

3. 查询元素： 使用键来获取对应的值。如果键不存在，可以使用 get() 方法，它会返回一个默认值（如 None 或自定义值）。

   print(my_dict["apple"])  # 输出：1
   print(my_dict.get("grape", 0))  # 输出：0，因为 "grape" 不在字典中
   

   Copy

4. 更新元素： 直接通过键来修改值。

   my_dict["apple"] = 4  # 更新值
   print(my_dict)  # 输出：{'apple': 4, 'banana': 2, 'orange': 3}
   

   Copy

5. 删除元素： 使用 del 或 pop() 来删除键值对。

   del my_dict["banana"]  # 删除键 "banana"
   print(my_dict)  # 输出：{'apple': 4, 'orange': 3}
   

   Copy

   value = my_dict.pop("orange", None)  # 删除并返回 "orange" 对应的值
   print(my_dict)  # 输出：{'apple': 4}
   print(value)  # 输出：3
   

   Copy

时间复杂度分析

• 查询和插入：对于字典的查询和插入操作，平均时间复杂度是 O(1)，即无论字典的大小如何，执行这些操作所需的时间几乎是恒定的。

• 删除：删除操作的时间复杂度也是 O(1)，但在最坏情况下（例如哈希冲突非常严重时），它可能退化为 O(n)，但这种情况非常少见。

Python 中的collections.Counter：

在 Python 中，Counter 是 collections 模块中的一个哈希表实现，属于 dict 字典的子类，用于统计元素的频率。它非常适合解决这类统计问题。

1. 键值对存储：Counter 存储的是数字及其出现次数的键值对。

示例代码：

# 创建一个 Counter 来统计数字的频率
numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
counter = Counter(numbers)

2. 快速访问：查询某个数字的出现次数是常数时间复杂度 O(1)。

示例代码：

# 快速查找某个数字的出现次数
print(counter[2])  # 输出 2，因为数字 2 出现了 2 次
print(counter[3])  # 输出 3，因为数字 3 出现了 3 次

主要操作的示例代码

在 Counter 中，除了常规的插入和访问操作外，还提供了许多便利的功能：

1. 插入或更新元素的频率：

from collections import Counter

counter = Counter()

# 插入元素
counter["apple"] += 1
counter["banana"] += 2

# 更新元素
counter["apple"] += 3

print(counter)  # 输出：Counter({'apple': 4, 'banana': 2})

2. 获取最常见的元素：

Counter 还提供了 most_common 方法，返回出现频率最高的元素及其频次。

from collections import Counter

numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
counter = Counter(numbers)

# 获取出现频率最高的前两个元素
print(counter.most_common(2))  # 输出：[(4, 4), (3, 3)]

3. 删除元素：

如果需要删除某个键值对，可以使用 del 或 subtract 方法。

from collections import Counter

numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
counter = Counter(numbers)

# 删除数字 2
del counter[2]

# 减去某个元素的频率
counter.subtract([3])

print(counter)  # 输出：Counter({4: 4, 3: 2, 1: 1})

4. 统计多个元素：

Counter 也支持对多个 Counter 进行合并，使用 + 或 update() 方法。

from collections import Counter

counter1 = Counter([1, 2, 3])
counter2 = Counter([3, 4, 5])

# 合并两个 Counter
combined_counter = counter1 + counter2
print(combined_counter)  # 输出：Counter({3: 2, 1: 1, 2: 1, 4: 1, 5: 1})

时间复杂度计算

在编写程序时，分析其时间复杂度（Time Complexity）是评估程序效率的重要手段。时间复杂度描述了程序运行时间与输入规模之间的关系，通常使用大O符号表示（如O(n)、O(n²)等）。下面将详细解释时间复杂度的概念，并分析这段代码的时间复杂度。

时间复杂度基础知识

OJ一般Python 1秒大概能跑1e7量级。

x = int(input())
ans = 0
for i in range(1, x + 1):
    ans += 1
print(ans)

对于这个简单的代码，x < 1e7 , 运行不会超时 ， x > 1e7 , 运行超时。

时间复杂度衡量的是算法执行所需的时间增长率，随着输入规模的增加，算法的运行时间如何变化。常见的时间复杂度包括：

O(1)：常数时间，无论输入规模多大，执行时间保持不变。

O(log n)：对数时间，随着输入规模增加，执行时间按对数增长。例如二分操作。

O(n)：线性时间，执行时间与输入规模成正比。

O(n log n)：线性对数时间，常见于高效排序算法如快速排序、归并排序。

O(n²)：平方时间，常见于简单的嵌套循环，如冒泡排序。

如何计算时间复杂度：

1. 识别基本操作：确定算法中最频繁执行的操作，如循环中的语句、递归调用等。

2. 计算基本操作的执行次数：根据输入规模，计算这些操作随着输入增长的次数。

3. 忽略低阶项和常数系数：在大O表示法中，只保留增长最快的项，忽略常数和低阶项。

对于一般情况

• $n$ = $10^5$ 或 n = $10^6$ 左右考虑 $O(n log n)$ 以下的做法
• $n$ = $5*10^3$ 左右考虑 $O(n²)$ 以下的做法
• $n$ = $10^2$ 左右考虑 $O(n³)$ 以下的做法
• $n$ = $20$ 以下考虑 $O(2^n)$ 以下的做法

对于当前题目而言，$Q = n = 10^{5}$，大家最直接能想到的做法是如下：考虑对于每次查询去遍历一遍所有数，复杂度为 $O(n * Q) = 10^{10}$，根据上面的 $1e7$ 定理，显然 $1$ 秒钟是跑不完的，下面让我们试试把下面这个淳朴的解法提交到 $OJ$ 上试试：

n, Q = map(int, input().split())  # 读取 n 和 Q 的值

numbers = list(map(int, input().split()))  # 读取口袋中的 n 个数字

# 处理每个查询
for _ in range(Q):
    x = int(input())  # 读取查询的数字
    count = 0  # 初始化计数器
    
    # 遍历整个口袋，统计 x 出现的次数
    for num in numbers:
        if num == x:
            count += 1
    
    print(count)  # 输出结果

可以看见，OJ反馈为超时。

题解

题面分析

本题要求在一个包含 $n$ 个整数的口袋中，回答 $Q$ 个查询，每个查询询问一个特定数字在口袋中出现的次数。由于 $n$ 和 $Q$ 的范围都较大（最大可达 $10^5$），因此需要高效的方法来预处理数据，以便快速回答查询。

思路分析

为了高效地回答每个查询，我们可以采用哈希表（Hash Table）的方式来统计每个数字出现的次数。具体步骤如下：

数据预处理：

遍历口袋中的所有数字，将每个数字及其出现次数存储在哈希表中。
由于数字的范围较大（$-10^9 \leq c \leq 10^9$），直接使用数组存储不切实际，因此使用哈希表能够有效地处理稀疏的数据。

# 统计每个数字出现的次数
count_map = Counter(numbers)

查询处理：

对于每个查询数字，直接在哈希表中查找其出现次数。
如果哈希表中不存在该数字，则说明其出现次数为 0。

# 处理每个查询
for _ in range(Q):
    num = int(input())  # 读取查询的数字
    print(count_map.get(num, 0))  # 输出该数字的出现次数

选择合适的哈希表：

在 Python 中，可以使用 Counter 来实现哈希表，Counter 提供了平均 O(1) 的查找和插入时间复杂度。
由于 Counter 的键值类型为整数，性能较为理想。

总体时间复杂度为 O(n + Q)。

代码实现

from collections import Counter

def main():
    # 读取 n 和 Q 的值
    n, Q = map(int, input().split())
    
    # 读取口袋中的 n 个数字
    numbers = list(map(int, input().split()))
    
    # 使用 Counter 来统计每个数字的出现次数
    count_map = Counter(numbers)
    
    # 处理每个查询
    for _ in range(Q):
        # 读取查询的数字
        num = int(input())
        
        # 输出该数字出现的次数，如果没有出现过则输出 0
        print(count_map.get(num, 0))

if __name__ == "__main__":
    main()