arrays - 距离可被整数整除的点对

Question

我遇到了一个面试问题，尽管我一直在尝试自己解决它，但我认为我需要一些帮助。

我有一个整数数组(正数和负数)代表空间中的点，两点之间的距离定义为 abs(A[i]-A[j])，我需要检查该距离可以被给定的整数 M 整除。

情况是这样的:

数组:[-3 -2 1 0 8 7 1]

M = 3

abs(A[1]-A[2]) = 3(例如它可以被整数整除)

复杂度应该是O(N+M)，空间O(M)

现在就是这些问题

1) 我知道有一种方法可以考虑所有的夫妇，而不用使用带有两个“for 循环”的明显解决方案，因为复杂度将是 N^2，这是不可取的，但我不知道如何做吧

2) 复杂度 O(N+M) 意味着我需要使用两个 for 循环而不是一个在另一个循环中？(我的意思是两个单独的 for 循环)，我在这里试图理解的是，如果给出的复杂度可以指导我会选择我应该使用的最佳算法。

3) 当规范说整数名称为 M 且复杂度为 O(N+M) 时，这是否意味着整数 M 和复杂度之间存在关系，或者它只是名称为的一种情况一样吗？

4)怎么做？

我希望我已经足够清楚了，如果没有，请告诉我，我会尝试更好地解释自己。

好的，让我们看看我是否理解正确这就是我目前正在尝试的:

int testCollection[7];

testCollection[0] = -3;
testCollection[1] = -2;
testCollection[2] = 1;
testCollection[3] = 0;
testCollection[4] = 8;
testCollection[5] = 7;
testCollection[6] = 1;

int arrayCollection[7];

for (unsigned int i = 0; i < 7; i++)
{
    arrayCollection[i] = 1000;
}

for (unsigned int i = 0; i < 7; i++)
{

    arrayCollection[i] = testCollection[i]%3;

} 

arrayCollection 现在包含:[0, -2, 1, 0, 2, 1 ,1 ]

我第二次不明白你的意思，你能说得更具体一点吗？想象一下我是一个 child :)

干杯

附注我不想打扰你太多，所以如果你愿意，你可以指点我一些我可以阅读的关于这个主题的文档，不幸的是谷歌搜索我没有找到太多。

Answer 1

两个点具有相同的 mod M 当且仅当它们相距 M 的整数倍时。因此，制作一个大小为 mod M 的整数数组 A，并为每个这样的整数 N[i] 遍历 N 整数，影响 A[N[i] % M]++。

最后，如果任何条目是>1，那么至少有一对整数是M的倍数。

要实际提取解决方案(即，获取相距 k*M 的值，而不是简单地知道有一些值)，您可以将整个 A 初始化为MAXINT，并在第一次看到特定的 mod M 时将值分配给 A。第二次你有了一对有效的值(value)观。