{"id":2347,"date":"2018-03-24T12:11:52","date_gmt":"2018-03-24T19:11:52","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2347"},"modified":"2018-03-24T12:32:19","modified_gmt":"2018-03-24T19:32:19","slug":"leetcode-447-number-of-boomerangs","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-447-number-of-boomerangs\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 447. Number of Boomerangs"},"content":{"rendered":"

Problem<\/h1>\n
\n
\n

Given\u00a0n<\/i>\u00a0points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points\u00a0(i, j, k)<\/code>\u00a0such that the distance between\u00a0i<\/code>\u00a0and\u00a0j<\/code>\u00a0equals the distance between\u00a0i<\/code>\u00a0and\u00a0k<\/code>\u00a0(the order of the tuple matters<\/b>).<\/p>\n

Find the number of boomerangs. You may assume that\u00a0n<\/i>\u00a0will be at most\u00a0500<\/b>\u00a0and coordinates of points are all in the range\u00a0[-10000, 10000]<\/b>\u00a0(inclusive).<\/p>\n

Example:<\/b><\/p>\n

Input:<\/b>\r\n[[0,0],[1,0],[2,0]]\r\n\r\nOutput:<\/b>\r\n2\r\n\r\nExplanation:<\/b>\r\nThe two boomerangs are [[1,0],[0,0],[2,0]]<\/b> and [[1,0],[2,0],[0,0]]<\/b>\r\n<\/pre>\n<\/div>\n<\/div>\n
Solution: HashTable<\/strong><\/h1>\n
For each point, compute the distance to the rest of the points and count.<\/p>\n
if there are k points that have the same distance to current point, then there are P(k,2) = k*k-1 Boomerangs.<\/p>\n
for example, p1, p2, p3 have the same distance to p0, then there are P(3,2) = 3 * (3-1) = 6\u00a0Boomerangs<\/p>\n
(p1, p0, p2), (p1, p0, p3)<\/p>\n
(p2, p0, p1), (p2, p0, p3)<\/p>\n
(p3, p0, p1), (p3, p0, p2)<\/p>\n
C++<\/p>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 210 ms (beats 83.33%)\r\nclass Solution {\r\npublic:\r\n  int numberOfBoomerangs(vector<pair<int, int>>& points) {\r\n    int ans = 0;\r\n    for (int i = 0; i < points.size(); ++i) {\r\n      unordered_map<int, int> dist(points.size());\r\n      for (int j = 0; j < points.size(); ++j) {\r\n        const int dx = points[i].first - points[j].first;\r\n        const int dy = points[i].second - points[j].second;        \r\n        ++dist[dx * dx + dy * dy];\r\n      }\r\n      for (const auto& kv : dist)\r\n        ans += kv.second * (kv.second - 1);      \r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n
Solution 2: Sorting<\/strong><\/h2>\n
dist = [1, 2, 1, 2, 1, 5]<\/p>\n
sorted_dist = [1, 1, 1, 2, 2, 5], 1*3, 2*2, 5*1<\/p>\n
ans = 3*(3-1) + 2 * (2 – 1) * 1 * (1 – 1) = 8<\/p>\n
Time complexity: O(n*nlogn)<\/p>\n
Space complexity: O(n)<\/p>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 150 ms (beats 98.52%)\r\nclass Solution {\r\npublic:\r\n  int numberOfBoomerangs(vector<pair<int, int>>& points) {\r\n    const int n = points.size();\r\n    int ans = 0;\r\n    vector<int> dist(points.size());\r\n    for (int i = 0; i < n; ++i) {   \r\n      for (int j = 0; j < n; ++j) {\r\n        const int dx = points[i].first - points[j].first;\r\n        const int dy = points[i].second - points[j].second;    \r\n        dist[j] = dx * dx + dy * dy;\r\n      }\r\n      \r\n      std::sort(dist.begin(), dist.end());\r\n      \r\n      for (int j = 1; j < n; ++j) {\r\n        int k = 1;\r\n        while (j < n && dist[j] == dist[j - 1]) { ++j; ++k; }\r\n        ans += k * (k - 1);\r\n      }\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Problem Given\u00a0n\u00a0points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points\u00a0(i, j, k)\u00a0such that the distance between\u00a0i\u00a0and\u00a0j\u00a0equals the distance…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127,70],"tags":[130,222,82,269],"class_list":["post-2347","post","type-post","status-publish","format-standard","hentry","category-geometry","category-hashtable","tag-distance","tag-easy","tag-hashtable","tag-pairs","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2347","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2347"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2347\/revisions"}],"predecessor-version":[{"id":2353,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2347\/revisions\/2353"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2347"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2347"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2347"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}