447号问题

来源：4-6 灵活选择键值 Number of Boomerangs

幕布斯1098637

2019-05-04

老师，你好。没理解“当有n个点到某点的距离相等的时候，用res += n *(n-1)"，难道不是应该是res += factorial(n) 吗？

写回答

1回答

liuyubobobo

2019-05-04

我理解你的问题是这段话：

for(unordered_map<int, int>::iterator iter = record.begin() ; iter != record.end() ; iter ++)    
    res += (iter->second) * (iter->second - 1);

在循环中，我们知道，距points[i]这个点的距离是iter->first的点，有iter->second这么多个。

那么，我们可以获得多少个三元组，满足题目条件呢？即i, j, k, ij的距离等于ik的距离？我们只需要取j和k就好了。（外层循环在遍历i）

j有iter->second这么多取法。取完j，k还有iter->second - 1这么多取法。

所以：res += (iter->second) * (iter->second - 1);

继续加油！：）

liuyubobobo

慕工程4033812

交换j和k的距离是允许的。题目的测试用例说明了这一点。但定义上，这不是这个三元组的排列或者组合。

2019-06-05

共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 2

回答 1

回答 1

回答 1

回答 1