447. Number of Boomerangs的C++解法

xiaoxiao2021-02-27  156

一开始感觉数据规模不大,没多想就直接用三个for暴力比较寻找,结果超时了。然后想了一下这个题问的是有还是没有(有几个),而不需要分别列出来是哪几个,所以可以使用哈希表的思路,固定点i,计算所有j和它的距离并记录到一个哈希表中,记录的过程中如果出现重复就+2。

int numberOfBoomerangs(vector<pair<int, int>>& points) { int booms = 0; for (auto &p : points) { unordered_map<double, int> ctr(points.size()); for (auto &q : points) booms += 2 * ctr[hypot(p.first - q.first, p.second - q.second)]++; } return booms; }

其中hypot函数是计算直角三角形斜边的函数,表达式 booms += 2 * ctr[hypot(p.first - q.first, p.second - q.second)]++的意思是每有一个新的点和固定点的距离与之前的点相同,都会和之前的每一个点形成2个pair。

另外作者说一开始初始化ctr可以提升速度:

Submitted five times, accepted in 1059, 1022, 1102, 1026 and 1052 ms, average is 1052.2 ms. The initial capacity for ctr isn't necessary, just helps make it fast. Without it, I got accepted in 1542, 1309, 1302, 1306 and 1338 ms.

转载请注明原文地址: https://www.6miu.com/read-16849.html

最新回复(0)