A国和B国正在打仗,他们的目的是n块土地。现在,A国和B国暂时休战,为了能合理分配这一些土地,AB国开始协商。 A国希望得到这n块土地中的p块土地,B国希望得到这n块土地中的q块土地。每个国家都将自己希望得到的土地编号告诉了小团和小美——两位战争调和人。 你需要帮小团和小美计算,有多少块土地是只有A国想要的,有多少块土地是只有B国想要的,有多少块土地是两个国家都想要的。
输入第一行包含三个整数n,p,q,含义如题意所示 接下来一行p个整数,空格隔开,第i个整数代表A国需要的土地编号 a_i 接下来一行q个整数,空格隔开,第i个整数代表B国需要的土地编号 b_i 土地编号从q开始,n结束。
输出包含三个数,只有A国想要的土地数,只有B国想要的土地数,两个国家都想要的土地数。
5 3 3 1 2 3 3 4 5
2 2 1
考点:哈希
限制 1 秒 / 256MB | 标准输入输出
推荐方向:哈希
本题切入点
把双方想要的土地编号放进集合,分别统计只在 A、只在 B、两者都有的数量。
用哈希表把「查找/计数」的开销降到 O(1) 均摊。
思路框架(哈希 通法 · 非本题专属)
实现要点:Python 用 dict / collections.Counter / defaultdict;C++ 用 unordered_map。
复杂度:时间 O(n) 均摊 | 空间 O(n)
该范式的通法易错点
样例 1:输入 5 3 3 / 1 2 3 / 3 4 5 → 输出 2 2 1
1,2号土地只有A想要,4,5号土地只有B想要,3号土地都想要
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:美团2023校招技术第5场编程题。