【算法刷题——回旋镖数量(力扣)】

发布时间:2024年01月09日

题目传送门

题目:给定平面上 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

提示:

  1. n == points.length
  2. 1 <= n <= 500
  3. points[i].length == 2
  4. -104 <= xi, yi <= 104
  5. 所有点都 互不相同

我的解法

class Solution {
public:
	// 欧氏距离
    int osDistance(vector<int> point1, vector<int> point2){
        return (point1[0]-point2[0])*(point1[0]-point2[0]) + (point1[1]-point2[1])*(point1[1]-point2[1]);
    }

    int numberOfBoomerangs(vector<vector<int>>& points) {
    	// 点的数量少于3不存在回旋镖,直接返回0
        if(points.size() < 3){
            return 0;
        }
        
        int count = 0;
        // 第一个循环用于获取第一个点
        for(auto base: points){
        	// 第二循环用于获取第二个点
            for(auto point1:points){
            	// 第二点不可以与第一个一样
                if(point1 == base){
                    continue;
                }
                // 计算第一个与第二点之间的距离
                int D1 = osDistance(base, point1);
				// 第三个循环用于获取第三点
                for(auto point2:points){
                	// 第三个点不可以第一、二个点重复
                    if(point2 == base or point2 == point1){
                        continue;
                    }
                    // 计算第一个点与第三个点之间的距离
                    int D2 = osDistance(base, point2);
                    // 如果D1==D2,增加一个回旋镖数量
                    if(D1 == D2){
                        count++;
                    }
                }
            }
        }
        return count;

    }
};

解题结果

超出时间限制
超出时间限制

分析

时间复杂度:O(n3)
空间复杂度:O(1)

官方题解

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>> &points) {
        int ans = 0;
        for (auto &p : points) {
            unordered_map<int, int> cnt;
            for (auto &q : points) {
                int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                ++cnt[dis];
            }
            for (auto &[_, m] : cnt) {
                ans += m * (m - 1);
            }
        }
        return ans;
    }
};

作者:力扣官方题解
链接:https://leetcode.cn/problems/number-of-boomerangs/solutions/994189/hui-xuan-biao-de-shu-liang-by-leetcode-s-lft5/
来源:力扣(LeetCode)

分析

通过使用哈希表,实现以空间换取时间。
假设某个距离的数量为m,由于题目说明需要考虑元组中元素的顺序,所以这个距离对应的回旋镖的数量为A2m
A2m = (m*(m-1)) / 2
时间复杂度:O(n2)
空间复杂度:O(n),哈希表占用的额外空间

更新日期

2024.1.8

参考

参考1链接

文章来源:https://blog.csdn.net/weixin_45111135/article/details/135454929
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。