[LeetCode] 447. Number of Boomerangs

轉自LeetCode

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]]

<Solution>

解題想法(參考資料)

• 計算每個點到其他點的距離，並將這個距離當作 key 存到 hashmap

• 對於每個 key，也就是一個特定的距離，不重複選兩個即為 Pn 取 2 = n!/ (n-2)! = n * (n-1)

• 複雜度為O(N^2)

code 如下

C++

	class Solution {
	public:
	int numberOfBoomerangs(vector<pair<int, int>>& points) {
	const int len = points.size();
	unordered_map<int, int> hashmap;
	int x, y;
	int ans = 0;
	for(int i = 0 ; i < len; i++) {
	for(int j = 0; j < len; j++) {
	if(i == j) {
	continue;
	}
	x = points[i].first - points[j].first;
	y = points[i].second - points[j].second;
	++hashmap[x*x+y*y];
	}
	for(const auto it: hashmap) {
	ans += it.second * (it.second - 1);
	}
	hashmap.clear();
	}
	return ans;
	}
	};

view raw numberOfBoomerangs.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public int numberOfBoomerangs(int[][] points) {
	final int len = points.length;
	HashMap<Integer, Integer> map = new HashMap<>();
	int x,y, key;
	int ans = 0;
	for(int i = 0; i < points.length; i++) {
	for(int j = 0; j < points.length; j++) {
	if(i == j) {
	continue;
	}
	x = points[i][0] - points[j][0];
	y = points[i][1] - points[j][1];
	key = x * x + y * y;
	map.put(key, map.getOrDefault(key, 0) + 1);
	}
	for(final int n : map.values()) {
	ans += n * (n-1);
	}
	map.clear();
	}
	return ans;
	}
	}

view raw numberOfBoomerangs.java hosted with ❤ by GitHub