algorithm - 在列表中查找重复项的最少检查

给定一个序列 (d1, d2, ..., dn)，我想评估所有 i != j 的乘积 (1 - Dij)，如果 di = dj，则 Dij = 1，否则为 0。

我的代码只在我检查 Dij 时

prod = 1;
for (int i=1; i<n; ++i) {
    for (int j=i; j<=n; ++j) {
        prod *= (1 - Dij);
    }
}

我知道当我得到 Dij=1 时我可以停止，但我想要做的是获得 Dij 的最小表达来检查。这样我就有了一个表达式，然后我可以使用不同的序列并对其进行评估。所以我知道我可以做 i<j 而不是 i != j 。所以我想扩展这个产品并在 n=3 时得到这样的东西:

(1 - D12) (1 - D13) (1 - D23) = 1 - D12 - D13 - D23 + D12*D13 + D12*D23 + D13*D23 - D12*D13*D23

但我能做的还有更多。这个表达式实际上总是等于

1 - D12 - D13 - D23 + 3 * D12*D13 - D12*D13*D23

我的问题是:

为什么是 D12 * D13 = D12 * D23？这总是正确的(意味着 d 序列是什么并不重要)但我真的不明白为什么，因为在我看来这意味着 D13 = D23 这并不总是正确的(这取决于 d 序列) .这是有助于使表达式更小的关系。

我怎样才能找到所有这样的关系并得到一个最小的表达？上面的表达式是最小的吗？我什至不知道。

最佳答案

您正在尝试确定 D 是否包含任何重复项。最终，这需要您将每个条目相互比较，这只是枚举两个元​​素的所有独特组合。这最终是 N*(N-1)/2 。您可以通过先对 D 进行排序然后搜索重复的相邻对 ( O(N*log(N) ) 来做得更好，或者，假设您坚持一个有界整数范围，您可以使用位向量将其减少到线性时间，或者如果您是感觉冒险，基数排序。

关于algorithm - 在列表中查找重复项的最少检查，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7561655/