首页 > 代码库 > 447. 求回旋镖坐标的数量 NumberOfBoomerangs

447. 求回旋镖坐标的数量 NumberOfBoomerangs

2024-08-31 19:01:16   226人阅读

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 iand 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]]
题意：定义一种类似“回形标”的三元组结构，即在三元组(i, j, k)中i和j之间的距离与i和k之间的距离相等。找到一组坐标数据中，可构成几组这样的“回形标”结构。

思路：遍历每一个点，用字典存储距离相同的点的数量
            根据数量，运用排列组合公式N*(N-1) ，计算回旋镖的可组成数量

For those that don‘t understand how groupCount * (groupCount + 1) became N * (N - 1):
algorithm actually sets groupCount to zero for the first point, 1 for the second point, etc. So, if N == groupCount + 1

N * (N - 1)
== (groupCount + 1) * ((groupCount + 1) - 1)
== (groupCount + 1) * (groupCount)
== groupCount * (groupCount + 1)
  1. static public int NumberOfBoomerangs(int[,] points) {
  2. 	int number = 0;
  3. 	int disSqrt = 0;
  4. 	int count = points.GetLength(0);
  5. 	for (int i = 0; i < count; i++) {
  6. 		Dictionary<int, int> dic = new Dictionary<int, int>();
  7. 		for (int j = 0; j < count; j++) {
  8. 			if (i == j) {
  9. 				continue;
  10. 			}
  12. 			disSqrt = (points[i, 0] - points[j, 0]) * (points[i, 0] - points[j, 0]) -
  13. 				(points[i, 1] - points[j, 1]) * (points[i, 1] - points[j, 1]);
  15. 			if (dic.ContainsKey(disSqrt)) {
  16. 				dic[disSqrt]++;
  17. 			} else {
  18. 				dic[disSqrt] = 0;
  19. 			}
  20. 		}
  22. 		foreach (int value in dic.Values) {
  23. 			number += value * (value + 1);
  24. 		}
  25. 	}
  26. 	return number;
  27. }


https://discuss.leetcode.com/topic/67102/c-hashtable-solution-o-n-2-time-o-n-space-with-explaination/2

https://discuss.leetcode.com/topic/68139/simple-java-solution-using-hashmap-beats-90/3



来自为知笔记(Wiz)


447. 求回旋镖坐标的数量 NumberOfBoomerangs


联系
我们