寻找点的子集，使得它们之间的距离是某个数的倍数。

Question

5

问题：给定一个数组A，表示一条线上的点，例如[5,-4,1,3,6]，以及一个数字M=3，找到A中距离彼此是M的倍数的点的最大子集。

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

明显的暴力解决方案是计算O(N^2)时间内每对点之间的距离，然后通过逐步构建子集来建立候选集。

是否有更有效的解决方案？

- curpickled

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- samgak · Accepted Answer

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

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

您需要小心处理负数，因为某些语言（例如PHP）对负数的模运算定义不同，但您希望mod（-4，3）计算为2，而不是-1。对于负数，您可以计算为（M -（-x mod M））mod M

您可以通过存储以模为键的列表的哈希映射来有效地分组数字。