[Swift]LeetCode447.回旋镖的数量|NumberofBoomerangs

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10340640.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

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

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

示例:

输入:
[[0,0],[1,0],[2,0]]

输出:
2

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

792ms

 1 class Solution {   
 2     func numberOfBoomerangs(_ points: [[Int]]) -> Int
 3     {
 4         var sum = 0
 5 
 6         for x in 0..<points.count {
 7             let m = points[x]
 8             
 9             var dic:Dictionary<Double,Int> = Dictionary.init()
10 
11             for y in 0..<points.count{
12                 let n = points [y]
13                 let p = m[0] - n[0]
14                 let q = m[1] - n[1]
15                 let k = sqrt(pow(Double(p), 2)+pow(Double(q), 2))
16                 var z = dic[k]
17                 if z == nil{
18                     z = 0
19                 }
20                 sum += z!*2
21                 dic[k] = z! + 1
22             }
23         }      
24         return sum
25     }
26 }

1072ms

 1 class Solution {
 2     func numberOfBoomerangs(_ points: [[Int]]) -> Int {
 3         let length = points.count
 4         guard length > 0 else {
 5             return 0
 6         }
 7         var count = 0
 8         
 9         for i in 0..<length {
10             var distanceInfo = Dictionary<Int,Int>()
11             
12             // 找出与i距离相同的点
13             for j in 0..<length {
14                 if i != j {
15                     let distance = self.distance(points[i], points[j])
16                     if let tempCount = distanceInfo[distance] {
17                         distanceInfo[distance] = tempCount + 1
18                     } else {
19                         distanceInfo[distance] = 1
20                     }
21                 }
22             }
23             
24             // 遍历字典，同i的距离相同的点大于2个
25             for (_, countOfDistance) in distanceInfo {
26                 count += (countOfDistance * (countOfDistance - 1))
27             }
28             
29         }
30         
31         return count
32     }
33     
34     func distance(_ point1: [Int], _ point2: [Int]) -> Int {
35         let x = point1[0] - point2[0]
36         let y = point1[1] - point2[1]
37         
38         return x * x + y * y
39     }
40 }

1204ms

 1 class Solution {
 2     func numberOfBoomerangs(_ points: [[Int]]) -> Int {
 3         var res:Int = 0
 4         for i in 0..<points.count
 5         {
 6             var m:[Int:Int] = [Int:Int]()
 7             for j in 0..<points.count
 8             {
 9                 var a:Int = points[i][0] - points[j][0]
10                 var b:Int = points[i][1] - points[j][1]
11                 if m[a * a + b * b] == nil
12                 {
13                      m[a * a + b * b] = 1
14                 }
15                 else
16                 {
17                      m[a * a + b * b]! += 1
18                 }               
19             }
20             
21             for val in m.values
22             {
23                 res += val * (val - 1);
24             }
25         }
26         return res
27     }
28 }

1208ms

 1 class Solution {
 2     func numberOfBoomerangs(_ points: [[Int]]) -> Int {
 3         var result = 0
 4         for index in 0..<points.count {
 5             var map: [Int: Int] = [:]
 6             for index2 in 0..<points.count {
 7                 if index2 == index {
 8                     continue
 9                 }
10 
11                 let distance = getDistance(points[index], points[index2])
12                 if let count = map[distance] {
13                     map[distance] = count + 1
14                 } else {
15                     map[distance] = 1
16                 }
17             }
18             
19             for count in map.values {
20                 result += count * (count - 1)
21             }
22         }
23 
24         return result
25     }
26 
27     func getDistance(_ point: [Int], _ point2: [Int]) -> Int {
28         let x = point[0] - point2[0]
29         let y = point[1] - point2[1]
30         return x * x + y * y
31     }
32 }

1560ms

 1 class Solution {
 2     func numberOfBoomerangs(_ points: [[Int]]) -> Int {  
 3         func getDistance(_ a: [Int], _ b: [Int]) -> Int {
 4             return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1])
 5         }        
 6         var map = [Int: Int]()
 7         var res = 0        
 8         for i in 0..<points.count {
 9             for j in 0..<points.count {
10                 if i == j { continue }                
11                 let distance = getDistance(points[i], points[j])                
12                 map[distance] = (map[distance] ?? 0) + 1
13             }            
14             for values in map.values {
15                 res += values * (values - 1)
16             }
17             map.removeAll()
18         }
19         return res
20     }   
21 }