【面试高频题】难度 1.5/5，简单常见的「哈希表」笔试/面试题
【面试高频题】难度 1.5/5，简单常见的「哈希表」笔试/面试题
宫水三叶的刷题日记
发布于 2022-04-06 21:42:39
发布于 2022-04-06 21:42:39
题目描述
这是 LeetCode 上的「447. 回旋镖的数量」，难度为「中等」。
Tag : 「哈希表」、「模拟」给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [x_i, y_i] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
返回平面上所有回旋镖的数量。
示例 1：
输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
示例 2：
输入：points = [[1,1],[2,2],[3,3]]
输出：2
示例 3：
输入：points = [[1,1]]
输出：0
提示：
- n == points.length
- 1 <= n <= 500
- points[i].length == 2
- 10^4 <= x_i, y_i <= 10^4
- 所有点都 互不相同
哈希表
数据范围为 500 ，三层循环的朴素做法显然会 TLE。
对于每个回旋镖三元组而言，本质上我们在统计给定 i 的情况下，与 i 距离相等的 (j, k) 组合个数为多少。
我们可以使用哈希表进行预处理，在统计以 i 为三元组第一位的回旋镖个数前，先计算出 i 和其余点的距离，并以 {距离:个数} 的形式进行存储，然后分别对所有的距离进行累加计数。
在计算距离时为了避免使用 sqrt，我们直接使用 x^2 + y^2 来代指两点间的距离。
代码：
class Solution {
public int numberOfBoomerangs(int[][] points) {
int n = points.length;
int ans = 0;
for (int i = 0; i < n; i++) {
Map<Integer, Integer> map = new HashMap<>();
for (int j = 0; j < n; j++) {
if (i == j) continue;
int x = points[i][0] - points[j][0], y = points[i][1] - points[j][1];
int dist = x * x + y * y;
map.put(dist, map.getOrDefault(dist, 0) + 1);
}
for (int dist : map.keySet()) {
int cnt = map.get(dist);
ans += cnt * (cnt - 1);
}
}
return ans;
}
}
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.447 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本文参与?腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-03-14，如有侵权请联系?cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录