给定一个数组，计算总和为 60 倍数的对

Question

给定一个数组，如何找到加起来为 60 或能被 60 整除的对（两个值）的数量。注意：必须比 O(N^2) 更快。

输入：[10,50,30,90] 输出：2 推理：10+50=60、30+90=120（120能被60整除）

输入：[60,60,60] 输出：3 推理：60 + 60 = 120, 60 + 60 = 120, 60 + 60 = 120

我下面的代码将在 O(N) 时间内运行，但我不知道如何处理彼此相等的对（即，如果数组中有 2 30 个值，则会向您的值添加 1计数器，但如果数组中有 3 30 个值，则计数器会加 3）。我想我应该创建一个组合函数（即 2C2 或 3C2），但这是一个线性函数，这不是会使函数回到 O(N^2) 吗？

values(myList) {
    var obj = {};
    var count = 0;

    // loop through array and mod each value and insert it into a dictionary
    myList.forEach((elem, index) => {
        if (!obj.hasOwnProperty(elem % 60)) {
            obj[elem % 60] = 1;
        } else {
            obj[elem % 60]++;
        }
    });

    for (var keys in obj) {
        if (obj.hasOwnProperty(60 - keys)) {
            if (60 - keys == keys) {
                // take care of pairs
                // obj[keys] = x --> xC2
            } else {
                count += Math.min(obj[keys], obj[60 - keys]);
                delete obj[keys]
                delete obj[60 - keys];
            }
        }
    }
    return count;
}

Answer 1

无需组合。这是简单的数学。

是

n * (n-1) / 2

。

假设您有 4 件商品

a

、

b

、

c

、

d

。

配对将是：

• （a，b）
• （a，c）
• （a，d）
• （b，c）
• （b，d）
• （c，d）

对于 4 项，我们有 4 * 3 / 2 = 6。

#更新：

改变

count += Math.min(obj[keys], obj[60 - keys]);

到

count += obj[keys] * obj[60 - keys];

考虑 2 个键 -

12

和

48

。

• 键

  12

  具有元素 - 12,72,132
• 键

  48

  有元素 - 48,108

从技术上讲，您正在为它们存储计数，即 3 和 2。 如果你观察的话，总数没有。我们可以组成的对是 3 * 2 = 6 而不是 Math.min(3,2);

Answer 2

您可以在 O(1) 时间内计算 nC2，因为 nC2 = ^n!/_(n−2)!·2! = ^{n·( n−1)·(n−2)!}/_(n−2)!·2! = ^n·(n−1)/_2! = ^n·(n−1)/₂.

也就是说，您可能需要考虑一种不同的方法：您可以在构建

count

时添加到

obj

，而不是使用单独的循环来基于

count

计算

obj

。这可能更直观，因为它消除了对特殊情况的需要。 （由你决定。）

顺便说一句，您的

if (60 - keys == keys)

测试不正确；它将检测

keys == 30

的情况，但不会检测

keys == 0

的情况。 （您可能还需要解决一些其他错误。）

Answer 3

如果我们计算每个元素可以与到目前为止看到的数字组成的对，我们可以使用简单的加法，而不是管理组合或微妙的边缘情况。

function f(A, m){
  const rs = new Array(m+1).fill(0);
  for (let x of A){
    if (rs[(m - x % m) % m])
      rs[m] += rs[(m - x % m) % m];
    rs[x % m]++;
  }
  return rs[m];
}

console.log(f([10, 50, 30, 30], 60));
console.log(f([30, 10, 50, 30, 30], 60));
console.log(f([1, 5, 3, 3, 6, 24], 6));

（顺便说一句，我不知道为什么要区分加起来为 60 的两个数字和总和可被 60 整除的值的对，因为前者包含在后者中。）

Answer 4

更新：这个解是n^2，所以这并不能回答原来的问题。

let values = [60,10,20,50,40,30, 120, 60, 10];

let count = 0;

for (let i = 0; i < values.length; i++){
    for (let j = i+1; j < values.length; j++){
        let v = values[i] + values[j];
        if (v == 60 || !(v % 60)){
            count++;
        }
    }    
}

更新2：

要使其成为 n + n*log(n)，可以使用 mod 值创建一棵排序树，然后迭代每个 mod 值并查找 60-mod 值以找到构成差异的对的数量。节点也可以优化存储重复次数。这能解决你的问题吗？

Answer 5

int numPairsDivisibleBy60(vector<int>& time) {
    
    int n = (int)time.size(), ans = 0;
    
    int freq[61]{};

    for(int i = 0; i < n; ++i) 
        freq[time[i] % 60]++;
    
    for(int i = 0; i <= 30; ++i) {
        if(freq[i] >= 1) {
            if(i == 0 or i == 30) {
                ans += freq[i] * 1LL * (freq[i] - 1) / 2;
            } else {
                ans += freq[60 - i] * freq[i];
            }
        }
    }
    
    return ans;

}