最有效的计算集合差的算法？
最有效的计算集合差的算法？
提问于 2022-06-13 12:35:18
当A集和B集被排序时，最有效的算法是计算A集和B集之间的差异。我如何用伪码实现它？
回答 2
Stack Overflow用户
回答已采纳
发布于 2022-06-13 13:03:54
在两个数组中使用索引，并比较这些索引的值。如果它们相等，则它们不在差中，这两个指标都可以用1递增。否则，最小值仅在两个集合中的一个，属于差。在这种情况下，只有该值的索引应该以1递增。
下面是基本JavaScript中的一个实现。它收集下列结果数组中的所有值：
仅发生在A中的
onlyInA：值，而不是仅发生在B中的BonlyInB：值，而不是A和B具有共同之处的AinBoth：值。
假设输入数组按升序排序。
function difference(a, b) {
let i = 0; j = 0;
let onlyInA = [];
let onlyInB = [];
let inBoth = [];
while (i < a.length || j < b.length) {
if (j >= b.length || a[i] < b[j]) {
onlyInA.push(a[i]);
i++;
} else if (i >= a.length || a[i] > b[j]) {
onlyInB.push(b[j]);
j++;
} else {
inBoth.push(a[i]);
i++;
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);
Stack Overflow用户
发布于 2022-06-14 11:49:28
对trincot算法的评论。
它工作正常吗？看起来，a或b数组的外部访问是有风险的.为了检查它，我将算法移植到C++。它可以很好地处理演示数据。但是，当我切换a和b的数据内容(所以a变成旧的b，b变成旧的a)时，我确实得到了一个超出范围的异常。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/72602958
复制相关文章
相似问题
腾讯云开发者
