微软一面面筋

刚刚才一面了微软面试。题目是假如有100个人，给你一个距离k，求有多少个三个人为一组的两两相互距离都小于k的组合。我有些懵逼，但是先来还是用brute force O(n3)做了，然后想半天没有想到更快的可行办法，然后想用相对于原点的相对距离进行排序，类似3sums的变形版解法，但是做了才知道没这么简单。然后面试官人还是很好，给我降低了难度，让我求在一条线上经过最多点有多少个。这个用slope做，然后x1-x2=0 或重合的时候，做了特殊处理，然后用dictionary记录每个slope的次数。
求助大神解第一道题！面试官说可以做到O(n^2)。


补充内容 (2019-6-25 20:06):
另外求点米，煮点米汤喝

补充内容 (2019-6-26 14:57):
是二维的

这题是并查集，两重遍历所有的组合，然后把距离小于k的两个人union，剩下的count就是数量

楼主，这个题是二维的吗？

个人感觉是这么做的：
首先用两层循环找到两两人的距离，然后设计一个图（二维数组表示），距离小于k的记为有路，距离大于k的无路。
之后既然是三人组两两小于k，那就是三人之间两两有路，即a-b,b-c，a-c
之后对图进行深度为2的bfs，比如，a搜到连着b，b搜到连着c，这时候检查a是否连着c，如果是，输出abc，如果不是，放弃c

如果面试官问优化的话，因为这是无向图，所以可以只记录一半的边，每次检查的时候严格按照ID小到大的顺序来。

我只能想到这儿了。