查找彼此之间距离是数字的倍数的点的子集

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]

您必须注意处理负数的方式，负数的模数运算在某些语言（例如 PHP）中的定义与其他语言不同，但您希望 mod(-4, 3) 评估为 2，而不是 -1 . 对于负数，您可以将其计算为 (M - (-x mod M)) mod M

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