距离可被整数整除的一对点

Question

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

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

所以情况是这样的：

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

中号=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 ]

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

干杯

ps 我不想过多打扰您，所以如果您愿意，可以向我指出一些我可以阅读的有关该主题的文档，不幸的是，谷歌搜索我没有找到太多。

Answer 1

两个点相同mod M当且仅当它们是间隔的整数倍M。A因此，创建一个大小为 的整数数组mod M，并循环遍历N整数，对于每个这样的整数N[i]，影响A[N[i] % M]++。

最后，如果有任何条目为>1，则至少存在一对相距为 的倍数的整数M。

要实际提取解决方案（即获取分开的值，k*M而不是简单地知道有一些值），您可以初始化整个Ato ，并在第一次看到特定值时MAXINT将该值分配给该值。第二次你就有了这对有效的价值观。Amod M