在O（n）时间内在数组中找到可分的和对

Question

你得到一个n整数a0, a1, .. an和一个正整数k数组。找到并打印(i,j)对的数量，其中i+j可以被k（这是i+j % k == 0）整除。这个问题来自here。

我们需要O(n)时间的解决方案。

一个解释是我们可以通过根据它们的mod k将元素分成桶来实现。例如，您有以下元素：1 3 2 6 4 5 9 and k = 3

mod 3 == 0 : 3 6 9
mod 3 == 1 : 1 4
mod 3 == 2 : 2 5

然后，据说：

现在，您可以像这样制作对：具有mod 3 == 0的元素将与具有（3 - 0）mod k = 0的元素匹配，因此mod 3 == 0列表中的其他元素，如下所示：（3,6 ）（3,9）（6,9）

进一步：

将有n *（n - 1）/ 2个这样的对，其中n是列表的长度，因为列表是相同的并且i！= j。 mod 3 == 1的元素将与（3 - 1）mod k = 2的元素匹配，因此mod 3 == 2列表中的元素，如下所示：（1,2）（1,5）（4,2） ）（4,5）

从(3, 6) (3, 9) (6, 9) ( all items in the 0th bucket be paired)起(a + b)% k = 0 = a % k + b % k是有道理的。

不清楚的是如何通过第1（mod 3 == 1）和第2（mod 3 == 2）桶中的元素组合生成其他对，为什么会有n *（n-1）/ 2对。还有另一种（更好的）方法吗？

这个问题适用于Math Stackexchange，它在发布问题之前我不知道。

Answer 1

我翻译C代码......

using namespace std;
int main(){

   int n;
   int k;
   cin >> n >> k;
   int a[n];
   int m[k];
   for(int i=0; i<k; i++)
       m[i]=0;
    for(int i = 0; i < n; i++){
       cin >> a[i];
        m[a[i]%k]++;
    }
    int sum=0;
    sum+=(m[0]*(m[0]-1))/2;
     for(int i=1; i<=k/2 && i!=k-i; i++){
         sum+=m[i]*m[k-i];
     }
    if(k%2==0)
        sum+=(m[k/2]*(m[k/2]-1))/2;
    cout<<sum;
    return 0;
}

进入Python：

def divisible_sum_pairs(n, k, a_list):
    m = [0] * len(a_list)
    for a in a_list:
        m[a % k] += 1

    sum = int(m[0] * (m[0] - 1) / 2)
    for i in range(1, int(k / 2) + 1):
        if i != k - 1:
            sum += m[i] * m[k - i]
    if k % 2 == 0:
        sum += m[int(k / 2)] * (m[int(k / 2)] - 1) / 2

    return sum

附：

print(divisible_sum_pairs(6, 3, [1,  3,  2,  6,  1,  2]))

你得到5

Answer 2

你有n * (n - 1) / 2对，因为每个人（n）都可以与其他人配对（n-1）;但由于顺序无关紧要，我们避免将镜像对除以2。

当分子被求和时，对相同商的余数也求和，但提醒不能超过商。 3在一个分区中提醒3实际上提醒了0。

答案非常聪明，通过低级优化可以使速度提高几个百分点;例如，实现一个专用的模块3，而不是依赖于%的通用算法;但你不能真正击败O(n)，因为你需要至少扫描一次每个元素，而且解决方案已经做得不多了。 （事实上​​，当你被要求写出结果时，在我看来你不能仅仅因为那个而在O(n^2)中做到这一点......）

这些问题都与python无关。你知道有一个math.stackexchange.com吗？

Answer 3

这个解决方案对我来说适用于较大的K值。对于较小的值，Laurent的解决方案更好。

def numPairsDivisibleByK（arr，k）：freq = [0 for i in range（k）] for i in arr：freq [i％k] + = 1

count = int(freq[0] * (freq[0] - 1) / 2)
for i in range(1, int(k / 2) + 1):
    if i == 0:
        count += int(freq[0] * (freq[0] - 1) / 2)
    elif float(i) == (k/2):
        count += int(freq[int(k/2)] * (freq[int(k/2)] - 1) / 2)
    else:
        count += int(freq[i] * freq[k-i])   

return count

print numPairsDivisibleByK（[30,20,150,100,40]，60）