algorithm - 找到彼此之间的距离是一个数的倍数的点的子集

Question

问题:给定一个数组A它代表一条线上的点，例如[5,-4,1,3,6] , 和一个数字 M=3 , 找到 A 内的最大点子集彼此之间的距离是 M 的倍数.

在这个例子中，两个可能的子集是[-4,5] (距离 9)和 [3,6] (距离 3)。

显而易见的蛮力解决方案是计算 O(N^2) 中每对点之间的距离时间，然后通过逐步构建子集来构建一组候选对象。

有没有更高效的解决方案？

Answer 1

遍历数组中的数字并计算每个数字的模数 M，然后按结果分组。最大的群是最大的子集。

例如[5,-4,1,3,6] 会给出 [2,2,1,0,0]

您必须注意如何处理负数，负数的模运算定义为 differently in some languages (例如 PHP)给其他人，但您希望 mod(-4, 3) 的计算结果为 2，而不是 -1。对于负数，您可以将其计算为 (M - (-x mod M)) mod M

您可以通过存储包含数字的列表的 HashMap 来有效地对数字进行分组，以模数为键。