距离可被整数整除的点对 [英] Pair of points with distance divisible by integer

问题描述

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

我有一个整数数组(正负)表示空间中的点，两点之间的距离定义为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)我知道有一种方法可以在不使用两个循环的显而易见的解决方案的情况下考虑所有的对，因为复杂性将是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]

我不明白你第二次说的是什么意思，你能说得更具体一点吗？想象我是个孩子：)

干杯

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

推荐答案

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

在结尾处，如果任何条目为>1，则至少有一对整数是M的倍数。

要实际提取解决方案(即，获取相隔k*M的值，而不是简单地知道有一些)，您可以将A的全部初始化为MAXINT，并在第一次看到特定的mod M时将该值赋给A。第二次获得有效的值对。

这篇关于距离可被整数整除的点对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！