先给出N个整数,然后查找整数d是否在这N个整数中出现过。 输入格式 第一行输入两个整数N(0<N<=1 000 000)和M(0<M<=10 000),N表示有N个整数,M表示要查找的整数d(0<=d<=500 000 000)的个数。接下来的一行输入N个整数x(0<=x<=500 000 000), 两个整数间空格隔开。接下来有M行,每行输入一个整数d,如果d在这N个整数中出现过,则输出"Yes"(不加引号),否则输出"No"。有多组测试数据。 输出格式 对于每个整数d,输出占一行。
时间: 2025-03-08 12:11:13 浏览: 30
为了实现这个功能,我们可以采用高效的算法来处理大量的数据,并且保证查询的速度足够快。下面是解决问题的一种高效方法:
### 解决方案
#### 步骤 1: 使用哈希表存储所有数字
由于需要快速判断某个元素是否存在,因此可以考虑使用 `set` 或者 `unordered_set` (Python 中可以直接使用集合 set),因为它们能在 O(1) 的平均时间复杂度内完成插入和查找操作。
#### 步骤 2: 预处理输入的数据
将所有的 N 个整数读入并存放到一个无序集合(哈希表)中。
#### 步骤 3: 进行 M 次查询
对于每一次给定的 d 值,在之前构建好的哈希表里查找该值的存在性,若存在则输出 "Yes" ,否则输出 "No".
以下是 Python 版本的具体代码实现:
```python
def process_queries():
import sys
input = sys.stdin.read
data = input().split()
index = 0
# 获取第一行的信息 - 整体数目N 和 查询次数M
n, m = int(data[index]), int(data[index + 1])
index += 2
# 构建包含n个元素的集合
numbers_set = {int(x) for x in data[index:index+n]}
index += n
results = []
for i in range(m):
query_num = int(data[index+i])
if query_num in numbers_set:
results.append("Yes")
else:
results.append("No")
print("\n".join(results))
# 主函数入口点
if __name__ == '__main__':
process_queries()
```
此程序首先一次性把全部的标准输入流读取到字符串列表中 (`data`),再根据题目描述解析出各个变量;利用集合类型构造了初始数据结构用于后续查询任务;最后遍历每一个待查项并将结果依次添加进最终的结果集当中。整个过程只需要两次完整的循环即可完成,确保了较高的运行效率。
请注意,实际提交时你需要调整标准输入的方式以适应评测系统的具体要求。
阅读全文