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

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;

} 

数组集合现在包含：[0，-2，1，0，2，1，1]

我不太明白你的意思，请再具体一些。可以像对待孩子一样解释吗？

如果你想了解更多信息，可以查看相关文档。抱歉，我无法提供链接。

- Fra

---

关于第3点，当整数为M时，复杂度应为O(N+M)。也就是说，当M更大时，时间会比M较小时更长。 - Atsby

Answer 1

若两个点的mod M相同，则它们之间的距离是M的整数倍。因此，创建大小为mod M的整数数组A，循环遍历N个整数，对于每个整数N[i]，进行A[N[i] % M]++操作。

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

要实际提取解决方案（即获取比简单知道有多组解决方案更具体的值k*M），可以将A的项初始化为MAXINT，并在第一次看到特定的mod M时将该值赋给A。第二次时您就得到了适用的一对值。

- Atsby

Answer 2

解决这个问题的关键是要认识到以下性质:

“所有距离点间隔为 `m`（或 `m` 的倍数）的位置，将会得到相同的模 `m` 结果。”

mod_res = num % m

这也意味着相反的情况成立，即“所有给定模数 m 的结果相同的点，实际上相差正好是 m 的倍数单位。”

以下是一个小图来说明你提出问题中的数字： 一旦我们理解了模运算性质与两点之间相对距离之间的关系，编写代码就很容易了。

我们只需要计算每个数字的模数结果，然后将具有相同模数结果的数字分组在一起。

def solution(array: List[int], m: int) -> int:
    # Maintain a hashmap of modulo_results and a list of numbers that resolve to that result
    modulo_results = defaultdict(list)
    for num in array:
        # Insert every number into the corresponding module_result list
        res = num % m
        modulo_results[res].append(num)
    
    # Now simply loop through every modulo_result list and find the longest one
    max_subset_size = 0
    max_subset = []
    for res, nums in modulo_results.items():
        if len(nums) > max_subset_size:
            max_subset_size = len(nums)
            max_subset = nums

    print(f"Max subset: {max_subset}")
    return max_subset_size

# print(solution([-3, -2, 1, 0, 8, 7, 1], m=3))
# Max subset: [-2, 1, 7, 1]
# 4

这个解决方案需要 O(n) 的时间和额外的 O(n) 空间。

- Aaron Alphonso

---

请问您是如何产生这种直觉的呢？这个问题通过模数属性变得非常琐碎，但我很难从直觉上理解它。 - Jyhonn

我认为这只是类似问题的经验。随着时间的推移，您会发展出知道在哪里应用什么逻辑的直觉。 - Aaron Alphonso

Answer 3

使用Kotlin实现，请查看以下内容：

fun largestSubSetDivisible(array: Array<Int>, m: Int):Int {
    val result = Array(1) { 1 }
    largestSubSetDivisible(array, m = m, result = result)
    return result[0]
}

fun largestSubSetDivisible(
    array: Array<Int>,
    arr: IntArray = IntArray(array.size) { 0 },
    i: Int = 0,
    m: Int,
    result: Array<Int> = Array(1) { 1 }
) {
    fun checkDivisionPair(array: List<Int>, m: Int): Boolean {
        for (j in 0 until array.size - 1) {
            if ((array[j] - array[j + 1]) % m != 0)
                return false
        }
        return true
    }
    if (i == array.size) {
        val count = arr.count { it == 1 }
        if (result[0] < count) {
            val ar = array.filterIndexed { index, _ -> arr[index] == 1 }
            if (checkDivisionPair(ar, m))
                result[0] = count
        }
        return
    }
    arr[i] = 0
    largestSubSetDivisible(array, arr, i + 1, m, result)
    arr[i] = 1
    largestSubSetDivisible(array, arr, i + 1, m, result)
}

- karthik varadharajan

Answer 4

这段代码的时间复杂度为O(M+N)，并且需要额外O(M)的空间。

modulus = (num,n)=>{
    if(num<0){
        do{
            num += n;
        }while(num<0);
    }
    return num%n;
}
var arr=[-5,-2,4,7,10,0,8],m=3,mod=[];
for(var index=0;index<m;index++){
    mod[index]=0;
}
for(index=0;index<arr.length;index++){
    mod[modulus(arr[index],m)]++;
}
mod.sort(function(a,b){
    return a-b;
});
if(mod[m-1] > 1){
    console.log(mod[m-1]);
}

最近在面试中遇到了这个问题。所以，我假设你的问题是我被问到的同一个问题的一部分。

- Aakash Arayambeth

Answer 5

基于C++的解决方案

int sol(std::vector<int> vec, int M)
{
    std::vector<int> mod(M);
    for (int p = 0; p < M; ++p) {
        mod[p] = 0;
    }
    for(int i : vec)
    {
        mod[(std::abs(vec[i]) % M)] = mod[(std::abs(vec[i]) % M)] + 1;
    }
    std::sort(mod.begin(), mod.end());
    return mod[M - 1];
}
int main( void )
{
    std::cout << sol({ -3, -2, 1, 0, 8, 7, 1 }, 3) << std::endl; // 4
    std::cout << sol({7, 1, 11, 8, 4, 10}, 8) << std::endl; // 2
    return 0;
}

- Prashant