问题 C: 查找
时间限制: 1 Sec 内存限制: 128 MB
提交: 5540 解决: 1803
[状态] [提交] [命题人:外部导入]
题目描述
给定一个集合,查找元素是否在集合中出现。
输入
每个测试用例由多行组成,第一行是两个整数n和m,两个数范围在1到100000之间。自第二行起一共有n+m个整数,其中前面n个整数代表集合的元素,随后的m个整数是待查询的数。所有的整数在范围[-2^31,2^31)内。
输出
对于每个待查询的数,如果在集合中则输出yes,否则输出no.
样例输入 Copy
5 3
7 9 3 2 -5
4 9 -5
5 3
-2 1 0 -2 1
0 -2 3
样例输出 Copy
no
yes
yes
yes
yes
no
提示
注意,需要快速的查找算法!效率不高的查找算法可能会超时!
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class search{
public static void main(String[] args) {
//输入
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
// 读取 n 和 m
int n = scanner.nextInt();
int m = scanner.nextInt();
scanner.nextLine(); // 消耗掉换行符!!!!!!!!!!!!!!!!!
// 创建 HashMap 来存储集合元素
Map<Integer, Boolean> set = new HashMap<>();
// 读取 n 个集合元素并添加到 HashMap 中
for (int i = 0; i < n; i++) {
int num = scanner.nextInt();
set.put(num, true); // 使用 true 作为 value 只是一个标记,因为我们只关心 key
if (i < n - 1) {
scanner.nextLine(); // 如果不是最后一个元素,消耗掉换行符
}
}
// 读取 m 个待查询的数并检查是否在集合中
for (int i = 0; i < m; i++) {
int query = scanner.nextInt();
if (set.containsKey(query)) {
System.out.println("yes");
} else {
System.out.println("no");
}
if (i < m - 1) {
scanner.nextLine(); // 如果不是最后一个查询,消耗掉换行符
}
}
}
scanner.close();
}
}