优化算法，每对在一个阵列

Question

对于一个简单的算法挑战，我必须作出一个算法来解决这个问题：

现在给你的ň整数数组，一个， a ，...，a， _n-1，和一个正整数，k。找到并打印的（I，J）的数量对其中我<Ĵ和一个_我 +一个_Ĵ是由ķ整除。

明显的穷举算法是为O（n 2 ）时间和O（1）空间（我想）。伪代码：

int count; 
for each (i in array) { 
    for each (j in array) { 
     if (i >= j) 
      continue; 

     if ((i + j) % k == 0) 
      count = count + 1; 
    } 
} 

我不认为有一种方法 - 有可能是:) - 不通过数组迭代2倍来算每对，因为每对（除了那些当然i >= j）有可能被k整除，所以我必须遍历所有这些。

那么，有没有什么办法来优化我的算法？

Answer 1

您可以遍历数组一次，并跟踪每个余数达到k-1的元素数，除以k。这需要O(k)空间，但允许您在O(n + k)步骤中解决问题，如果k很小，则该步骤会更好。

伪代码（AKA的JavaScript）：

function countDivisiblePairs(arr, k) { 
    const remainders = Array(k).fill(0); 
    for (let i = 0; i < arr.length; i++) { 
     remainders[ arr[ i ] % k ]++; 
    } 

    // Count the pairs of elements that were individually 
    // divisible by `k` (had a remainder of `0`), so 
    // added together they are still divisible by k 
    // 
    // `remainders[ 0 ]*remainders[ 0 ]` of them if we wanted all, but 
    // since we only want to count when i < j, so we subtract 
    // `remainders[0]` to get rid of the cases where `i = j` and then 
    // we divide by 2 to remove the cases where `i > j`. 

    let numPairs = (remainders[ 0 ]*remainders[ 0 ] - remainders[ 0 ])/2; 

    // Count the cases where the remainder wasn't 0, 
    // if the remainders sum to `k`, then the sum is divisible by `k`. 
    for (let i = 1; i <= k/2; i++) { 

     // Note that i + (k - i) = k, so each elements with a 
     // remainder of `i` can be paired with each element with 
     // a remainder of `k`, but, if `k` was even there will be a 
     // final iteration where `i = (k - i)`, so we need to add a 
     // special case to only count when `i < j`, we do it the same 
     // way as we did for the case when the remainder was 0. with 
     // the if statement `(2*i === k)` is another way of writing 
     // the expression `i === (k - i)`. 

     if (2*i === k) 
      numPairs += (remainders[ i ]*remainders[ i ] - remainders[ i ])/2; 
     else 
      numPairs += remainders[ i ]*remainders[ k - i ]; 
    } 
    return numPairs; 
} 

上面的代码假定有输入数组中没有重复。在这种情况下，您需要特别注意EG，[2,2,4,4,4], 2应该输出6，而不是输出10（[2,4,6,8,10], 2的正确输出），但它应该给你算法的精华。输出：

countDivisiblePairs([1,2,3,4,5,6,7,8], 2); // 12 
countDivisiblePairs([1,2,3,4,5,6,7,8], 3); // 10 
countDivisiblePairs([1,2,3,4,5,6,7,8], 4); // 6 
countDivisiblePairs([1,2,3,4,5,6,7,8], 5); // 6 

注意，在循环中的特殊情况只是发生在最后一次迭代，当k只有甚至，EG。如果k是4，那么当i = 2,i === (k - i)，所以如果我们没有特殊的处理，我们会计算额外的元素。 EG作为示例输出，其中我使用了k的4，有两个元素的剩余部分为2：[2,6]。如果我们没有额外的处理，它会说有四种方法将它们配对，总计为(2,2),(2,6),(6,2),(6,6)，但额外的逻辑减去了它们与它们自己配对的情况，所以我们剩下(2,6),(6,2)，然后除以2减去i > j的情况，所以你只剩下一对数：(2,6)。