美团 · 哈希 · 算法编程题
美团 哈希 时限 1 秒 / 256 MB

题目描述

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国想要的土地数,两个国家都想要的土地数。

样例共 1 组

样例 1 · 1,2号土地只有A想要,4,5号土地只有B想要,3号土地都想要
输入
5 3 3
1 2 3
3 4 5
输出
2 2 1

算法解析依据充分

考点:哈希

限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:哈希

本题切入点

把双方想要的土地编号放进集合,分别统计只在 A、只在 B、两者都有的数量。

用哈希表把「查找/计数」的开销降到 O(1) 均摊。

思路框架(哈希 通法 · 非本题专属)

  1. 一次遍历,把元素作为 key、出现次数/首次位置作为 value 存进哈希表。
  2. 第二次遍历(或边扫边查)拿到需要的信息。
  3. 注意哈希无序:需要按原顺序输出时要额外记录顺序。

实现要点: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场编程题。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解