Problem
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]]
Solution: HashTable
For each point, compute the distance to the rest of the points and count.
if there are k points that have the same distance to current point, then there are P(k,2) = k*k-1 Boomerangs.
for example, p1, p2, p3 have the same distance to p0, then there are P(3,2) = 3 * (3-1) = 6 Boomerangs
(p1, p0, p2), (p1, p0, p3)
(p2, p0, p1), (p2, p0, p3)
(p3, p0, p1), (p3, p0, p2)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 210 ms (beats 83.33%) class Solution { public: int numberOfBoomerangs(vector<pair<int, int>>& points) { int ans = 0; for (int i = 0; i < points.size(); ++i) { unordered_map<int, int> dist(points.size()); for (int j = 0; j < points.size(); ++j) { const int dx = points[i].first - points[j].first; const int dy = points[i].second - points[j].second; ++dist[dx * dx + dy * dy]; } for (const auto& kv : dist) ans += kv.second * (kv.second - 1); } return ans; } }; |
Solution 2: Sorting
dist = [1, 2, 1, 2, 1, 5]
sorted_dist = [1, 1, 1, 2, 2, 5], 1*3, 2*2, 5*1
ans = 3*(3-1) + 2 * (2 – 1) * 1 * (1 – 1) = 8
Time complexity: O(n*nlogn)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua // Running time: 150 ms (beats 98.52%) class Solution { public: int numberOfBoomerangs(vector<pair<int, int>>& points) { const int n = points.size(); int ans = 0; vector<int> dist(points.size()); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { const int dx = points[i].first - points[j].first; const int dy = points[i].second - points[j].second; dist[j] = dx * dx + dy * dy; } std::sort(dist.begin(), dist.end()); for (int j = 1; j < n; ++j) { int k = 1; while (j < n && dist[j] == dist[j - 1]) { ++j; ++k; } ans += k * (k - 1); } } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment