算法学习之查找表3

Jackey C/C++ 737 次浏览 , 没有评论

题目要求:

给定平面上 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
-104 <= xi, yi <= 104
所有点都 互不相同

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-boomerangs

解题代码:

// 时间复杂度: O(n^2)
// 空间复杂度: O(n)
class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>> &points) {
        int res = 0;
        for (int i = 0; i < points.size(); ++i) {
            unordered_map<int, int> record;
            for (int j = 0; j < points.size(); ++j) {
                if (j != i)
                    record[dis(points[i], points[j])]++;
            }

            for (unordered_map<int, int>::iterator iter = record.begin(); iter != record.end(); iter++) {
//                if (iter->second >= 2)
                res += (iter->second) * (iter->second - 1);
            }
        }
        return res;
    }

private:
    int dis(const vector<int> &pa, const vector<int> &pb) {
        return (pa[0] - pb[0]) * (pa[0] - pb[0]) + (pa[1] - pb[1]) * (pa[1] - pb[1]);
    }
};

 

发表评论

您的电子邮箱地址不会被公开。

Go