class Solution1(object):
def numberOfBoomerangs(self, points):
"""
first method is brute force , get all three tuple combination and calc whether condition is matched
TLE
"""
result = 0
for i in range(len(points)):
for j in range(len(points)):
if i == j: continue
for k in range(len(points)):
if j == k: continue
if self.calc_distance(points[i], points[j]) == self.calc_distance(points[i], points[k]):
result += 1
return result
def calc_distance(self, point1, point2):
return pow(point1[0] - point2[0], 2) + pow(point1[1] - point2[1], 2)
class Solution2(object):
def numberOfBoomerangs(self, points):
"""
use distance between two points as key, and the number of point pair as value, in each round , we build a new map for current point
for each point we calc how many other point with the same distance to it , and they(other points) can form a triple
and it's not necessary to judge whether i == j
beat 10%
"""
result = 0
from collections import defaultdict
for i in range(len(points)):
dict = defaultdict(int)
for j in range(len(points)):
if i == j: continue
dict[self.calc_distance(points[i], points[j])] += 1
for key in dict:
result += dict[key] * (dict[key] -1)
return result
def calc_distance(self, point1, point2):
return pow(point1[0] - point2[0], 2) + pow(point1[1] - point2[1], 2)
class Solution3(object):
def numberOfBoomerangs(self, points):
"""
Try not import other package and other function but not faster
beat 5%
"""
result = 0
for i in range(len(points)):
dict = {}
for j in range(len(points)):
dict[self.calc_distance(points[i], points[j])] = dict.get(self.calc_distance(points[i], points[j]), 0) +1
for key in dict:
result += dict[key] * (dict[key] -1)
return result
def calc_distance(self, point1, point2):
return (point1[0] - point2[0])**2 + (point1[1] - point2[1])**2
class Solution4(object):
def numberOfBoomerangs(self, points):
"""
For the solution mention above, we start from 0 in the second loop, it's not necessary
we can start from i+1, and update both start_node and end_node with the distance. In that case we need create a dict list instead of single dict one by one
1036 ms, faster than 75.17%
"""
res, length = 0, len(points)
dict_list = [{} for _ in range(length)]
for i in range(length):
for j in range(i+1, length):
distance = self.calc_distance(points[i], points[j])
dict_list[i][distance] = dict_list[i][distance] + 1 if distance in dict_list[i] else 1
dict_list[j][distance] = dict_list[j][distance] + 1 if distance in dict_list[j] else 1
for n in dict_list[i]:
res += dict_list[i][n] * (dict_list[i][n] -1)
return res
def calc_distance(self, point1, point2):
return (point1[0] - point2[0])**2 + (point1[1] - point2[1])**2
class Solution5(object):
def numberOfBoomerangs(self, points):
"""
Modify from solution4.
In solution4 , we count the point[i]' s result after update the dict, it's parallel with updating dict, it will cause time consumption doubled.
So while updating dict, we can also calc the result.
For each point's value length n, the result = n*(n-1), so we can use add operation before updating dict every time(1+2+..n-1) and muplitly 2 finally
804 ms, faster than 91.27%
"""
res, length = 0, len(points)
dict_list = [{} for _ in range(length)]
for i in range(length):
for j in range(i + 1, length):
distance = self.calc_distance(points[i], points[j])
if distance in dict_list[i]:
res += dict_list[i][distance]
dict_list[i][distance] +=1
else:
dict_list[i][distance] =1
if distance in dict_list[j]:
res += dict_list[j][distance]
dict_list[j][distance] += 1
else:
dict_list[j][distance] =1
return res*2
def calc_distance(self, point1, point2):
return (point1[0] - point2[0])**2 + (point1[1] - point2[1])**2
