idea網(wǎng)站開發(fā)上海網(wǎng)站建設(shè)開發(fā)
【LetMeFly】447.回旋鏢的數(shù)量:哈希表
力扣題目鏈接:https://leetcode.cn/problems/number-of-boomerangs/
給定平面上?n
對(duì) 互不相同 的點(diǎn)?points
,其中 points[i] = [xi, yi]
。回旋鏢 是由點(diǎn)?(i, j, k)
表示的元組 ,其中?i
?和?j
?之間的距離和?i
?和?k
?之間的歐式距離相等(需要考慮元組的順序)。
返回平面上所有回旋鏢的數(shù)量。
?示例 1:
輸入:points = [[0,0],[1,0],[2,0]] 輸出:2 解釋:兩個(gè)回旋鏢為 [[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
- 所有點(diǎn)都 互不相同
方法一:哈希表
第一重循環(huán)枚舉每個(gè) j j j點(diǎn)。對(duì)于points[j],使用一個(gè)哈希表,記錄所有的點(diǎn)到j(luò)點(diǎn)的距離的出現(xiàn)次數(shù)。然后遍歷哈希表,假設(shè)某距離出現(xiàn)了cnt次,那么就將 c n t × ( c n t ? 1 ) cnt\times(cnt-1) cnt×(cnt?1)累加到答案中。
- 時(shí)間復(fù)雜度 O ( l e n ( p o i n t s ) 2 ) O(len(points)^2) O(len(points)2)
- 空間復(fù)雜度 O ( l e n ( p o i n t s ) ) O(len(points)) O(len(points))
AC代碼
C++
class Solution {
public:int numberOfBoomerangs(vector<vector<int>>& points) {int ans = 0;for (vector<int>& p : points) {unordered_map<int, int> ma;for (vector<int>& q : points) {ma[(p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])]++;}for (auto [_, cnt] : ma) {ans += cnt * (cnt - 1);}}return ans;}
};
Python
# from typing import List
# from collections import defaultdictclass Solution:def numberOfBoomerangs(self, points: List[List[int]]) -> int:ans = 0for p in points:ma = defaultdict(int)for q in points:ma[(p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])] += 1for _, cnt in ma.items():ans += cnt * (cnt - 1)return ans
同步發(fā)文于CSDN,原創(chuàng)不易,轉(zhuǎn)載經(jīng)作者同意后請(qǐng)附上原文鏈接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/135464460