计算集合差异的最有效算法？

Question

当 A 组和 B 组都已排序时，计算 A 组和 B 组之间差异的最有效算法是什么？如何用伪代码实现它？

Answer 1

在两个数组中使用索引，并比较这些索引处的值。如果相等，则不存在差异，并且两个索引都可以加 1。 否则，最小值仅在两个集合之一中，并且属于差值。在这种情况下，只有该值的索引应该增加 1。

这是一个基本 JavaScript 的实现。它收集以下结果数组之一中的所有值：

• onlyInA

  ：仅出现在 A 中，而不出现在 B 中的值

• onlyInB

  ：仅出现在 B 中的值，而不出现在 A 中

• inBoth

  ：A 和 B 的共同值。

假设输入数组按升序排序。

function difference(a, b) {
    let i = 0; j = 0;
    let onlyInA = [];
    let onlyInB = [];
    let inBoth = [];
    while (i < a.length && j < b.length) {
        if (a[i] < b[j]) {
            onlyInA.push(a[i]);
            i++;
        } else if (a[i] > b[j]) {
            onlyInB.push(b[j]);
            j++;
        } else {
            inBoth.push(a[i]);
            i++;
            j++;
        }
    }
    onlyInA.push(...a.slice(i));
    onlyInB.push(...b.slice(j));
    return [onlyInA, onlyInB, inBoth];
}

// Demo run
let a = [2,3,5,7,11,13,17,19,23,29,31,37];
let b = [1,3,7,15,31];
let [onlyInA, onlyInB, inBoth] = difference(a, b);
console.log("only in A:", ...onlyInA);
console.log("only in B:", ...onlyInB);
console.log("in both:", ...inBoth);

Answer 2

评论 trincot 算法。

工作正常吗？看起来，存在对 a 或 b 数组进行越界访问的风险。为了验证这一点，我将该算法移植到了 C++ 中。它与演示数据配合得很好。但是当我交换 a 和 b 的数据内容时（因此 a 变成了旧的 b，b 变成了旧的 a），我确实遇到了越界异常。