LeetCode447-回旋镖的数量

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/number-of-boomerangs/

中文链接：https://leetcode-cn.com/problems/number-of-boomerangs/

题目详述

给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。

示例:

1
2
3
4
5
6
7
8
输入:
[[0,0],[1,0],[2,0]]

输出:
2

解释:
两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

题目详解

  • (i, j, k) 中 i 和 j 之间的距离和 i 和 k 之间的距离相等，关键在于 i，可以固定 i。
  • 遍历 points，对于每一个 i，遍历 points， 运用 HashMap 统计 i 和 j之间的距离相同的个数（因为距离为小数，可以改为存储距离的平方，且不会溢出）。
  • 假设同一距离出现 n 次，易知此距离上的回旋镖数量为 n * (n - 1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class LeetCode_00447 {

    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        for (int i = 0; i < points.length; ++i) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int j = 0; j < points.length; ++j) {
                if (i != j) {
                    int dis = getDistance(points[i], points[j]);
                    map.put(dis, map.getOrDefault(dis, 0) + 1);
                }
            }
            for (int num : map.values()) {
                res += num * (num - 1);
            }
        }
        return res;
    }

    private int getDistance(int[] a, int[] b) {
        int x = a[0] - b[0];
        int y = a[1] - b[1];
        return x * x + y * y;
    }
}

重复运用 HashMap，每次用完进行 clear 可以提高效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class LeetCode_00447 {

    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < points.length; ++i) {
            for (int j = 0; j < points.length; ++j) {
                if (i != j) {
                    int dis = getDistance(points[i], points[j]);
                    map.put(dis, map.getOrDefault(dis, 0) + 1);
                }
            }
            for (int num : map.values()) {
                res += num * (num - 1);
            }
            map.clear();
        }
        return res;
    }

    private int getDistance(int[] a, int[] b) {
        int x = a[0] - b[0];
        int y = a[1] - b[1];
        return x * x + y * y;
    }
}
  • 同一距离出现 n 次，易知此距离上的回旋镖数量为 n * (n - 1)；同一距离出现 n + 1 次，易知此距离上的回旋镖数量为 (n + 1) * n。两者的差值为 2 * n，也就是说，相同距离加一，回旋镖的数量只需要在原来的基础上加上 2 * n。
  • 在统计的过程中累计结果，避免最后遍历 HashMap 的过程，可以提高效率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class LeetCode_00447 {

    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < points.length; ++i) {
            for (int j = 0; j < points.length; ++j) {
                if (i != j) {
                    int dis = getDistance(points[i], points[j]);
                    Integer v = map.get(dis);
                    if (v == null) {
                        map.put(dis, 1);
                    } else {
                        map.put(dis, v + 1);
                        res += v << 1;
                    }
                }
            }
            map.clear();
        }
        return res;
    }

    private int getDistance(int[] a, int[] b) {
        int x = a[0] - b[0];
        int y = a[1] - b[1];
        return x * x + y * y;
    }
}