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]]
C Solution:
struct He {
int dist;
int count;
struct He *next;
};
struct Ht {
int size;
struct He **list;
};
struct Ht *create() {
struct Ht *ht = malloc(sizeof(struct Ht));
ht->size = 1000;
ht->list = calloc(ht->size, sizeof(struct He *));
return ht;
}
void insert(struct Ht *ht, int dist) {
int ind = dist % ht->size;
struct He *p = ht->list[ind];
while (p) {
if (p->dist == dist) {
p->count++;
return;
}
p = p->next;
}
p = malloc(sizeof(struct He));
p->dist = dist;
p->count = 1;
p->next = ht->list[ind];
ht->list[ind] = p;
}
int numberOfBoomerangs(int** points, int pointsRowSize, int pointsColSize) {
int i, res = 0;
struct Ht *ht = create();
for (i = 0; i < pointsRowSize; i++) {
int j;
for (j = 0; j < pointsRowSize; j++) {
if (i == j) continue;
int dx = points[i][0] - points[j][0], dy = points[i][1] - points[j][1];
int dist = dx * dx + dy * dy;
insert(ht, dist);
}
for (j = 0; j < ht->size; j++) {
struct He *p = ht->list[j], *q;
while (p) {
q = p->next;
res += p->count * (p->count - 1);
free(p);
p = q;
}
ht->list[j] = 0;
}
}
return res;
}
Python Solution 1:
import collections
class Solution(object):
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
def dis(p1, p2):
return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1])
res = 0
for p in points:
d = collections.defaultdict(int)
for q in points:
d[dis(p, q)] += 1
for _dis in d:
res += d[_dis] * (d[_dis] - 1)
return res
Summary:
- The time complexity is at least O(N2), so don't overthink.
LeetCode: 447. Number of Boomerangs
近期评论