【力扣每日一题】力扣447回旋镖的数量

题目来源

力扣447回旋镖的数量

题目描述

给定平面上?n?对 互不相同 的点?points?，其中?points[i] = [xi, yi]?。回旋镖 是由点?(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 <= xi, yi <= 10^4
• 所有点都 互不相同

思路分析

1. 回旋镖是由(i, j, k)三个点组成的三元组表示的，我们可以取回旋镖的中心点 j?来表示这个回旋镖；
2. i 和 j 之间的距离与 j 与 k 之间的距离相等，所以我们可以使用 key 为距离，value 为与中心点距离为 key 值的数量的哈希表来保存距离及点个数。
3. 因为需要考虑顺序所以(i, j, k)与(k, j, i)是两个回旋镖，我们可以使用组合公式来计算 value 个点中取两个有多少中方式：value * (value - 1)。

p.s. 代码中的三元组为(j1, i, j2)

代码实现

java实现

public class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int count = 0;
        // 记录点到中心的距离及这个距离上点的数量
        Map<Integer, Integer> map = new HashMap<>();
        // 回旋镖中心点
        for (int i = 0; i < points.length; i++) {
            map.clear();
            // 保存距离及数量
            for (int j = 0; j < points.length; j++) {
                if (i == j) {
                    continue;
                }
                int distance = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0])
                        + ((points[i][1] - points[j][1])) * (points[i][1] - points[j][1]);
                map.put(distance, map.getOrDefault(distance, 0) + 1);
            }
            // 使用组合公式计算回旋镖数量
            for (Integer distance : map.keySet()) {
                Integer num = map.get(distance);
                count += num * (num - 1);
            }
        }
        return count;
    }
}

c++实现

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int count = 0;
        // 到中心点的距离以及这个距离上点的数量
        map<int,int> distanceCountMap;
        // i表示中心点
        for (int i = 0; i < points.size(); i++) {
            distanceCountMap.clear();
            // 计算点的数量
            for (int j = 0; j < points.size(); j++) {
                if (i == j) {
                    continue;
                }
                int distance = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0])
                    + ((points[i][1] - points[j][1])) * (points[i][1] - points[j][1]);
                distanceCountMap[distance] = distanceCountMap[distance] + 1;
            }
            // 使用组合公式计算回旋镖数量
            for (auto iterator : distanceCountMap) {
                int num = iterator.second;
                count += num * (num - 1);
            }
        }
        return count;
    }
};