這次要講的題目是Number of Boomerangs
題目網址 https://leetcode.com/problems/number-of-boomerangs/#/description
這一題小弟覺得不算是簡單的題目
(可能我數學不夠好XDD)
在此稍微說明一下題目：
給你一個包含n個tuple
(tuple的中文好像是數對，就是每一個tuple包含兩個數字x,y)
要在這n個tuple之中
找出符合像"boomerang"條件的組數量
也就是說從中抓任意三個點A.B.C
從A到B的距離"等於"從A到C的距離
其中(A,B,C)和(A,C,B)是不一樣的組合(考慮順序)
最多500個tuple
數值範圍介於-10000~10000
舉例來說
輸入：[[0,0],[1,0],[2,0],[0,1]]符合boomerang的條件有
[1,0],[0,0],[2,0]
[2,0],[0,0],[1,0]
[0,0],[1,0],[0,1]
[0,0],[0,1],[1,0]
總共4種
因此輸出4
《以下是我的解題方式》
一開始我想了很久不知從何下手
用手算還算容易
後來一直盯著上面的結果看
就大致想到了
先任意抓出兩個點算長度
固定前面的點讓他去跟剩下的點算長度後做比較
有找到一樣的就把結果存起來
不過這樣有個問題是
時間複雜度會到O(n^3)
(最外面的一層是控制第一個點，中間那層控制第二個點，最裡面那層控制第三個點)
在別的相似題中會出現TLE的狀態
後來求助大神後
改成以下的作法
一樣先計算其中兩個點的長度
藉由unordered_map的container來做table
key：兩點的長度(平方)
value：有幾組tuple是這個長度
每算完一次兩點長度
就把這長度對應的那一欄+1
算完之後
由排列組合的概念：
對於每固定一個點之後
在剩下的點中距離這個點為___的個數是n
則表示能構成boomerange的種類有
P(n,2) = n! / (n-2)! = n * (n-1)
再把答案加總即可
舉一個較簡單的例子
輸入：[[0,0],[1,0],[2,0],[0,1]]
以上面的例子來說
所有的可能性為
[0,0],[1,0] → 1
[0,0],[0,1] → 1
[0,0],[2,0] → 4
2! / 0! = 2
[1,0],[0,0] → 1
[1,0],[2,0] → 1
[1,0],[0,1] → 2
2! / 0! = 2
[2,0],[0,0] → 4
[2,0],[1,0] → 1
[2,0],[0,1] → 5
No~
[0,1],[0,0] → 1
[0,1],[1,0] → 2
[0,1],[2,0] → 5
No~
答案為2+2=4
《曾經錯過的測資》
無
《程式碼在這》
【小提醒：盡量自己先參考上面的想法寫出來，這樣比較不會有背程式碼的概念】
class Solution {
public:
int numberOfBoomerangs(vector<pair<int, int>>& points) {
int ans=0;
for(int i=0;i<points.size();++i){
unordered_map<long,int> res;
for(int j=0;j<points.size();++j){
if(i==j) continue;//
int x = points[i].first - points[j].first;
int y = points[i].second - points[j].second;
long distance = x*x + y*y;
++res[distance];
}
for(auto& ptr : res){
if(ptr.second>1){
ans += (ptr.second * (ptr.second -1));
}
}
}
return ans;
}
};
