當兩個集合都被排序時，計算 A 和 B 集合之間差異的最有效演算法是什么？如何用偽代碼實作它？
uj5u.com熱心網友回復：
在兩個陣列中使用索引，并比較這些索引處的值。如果它們相等，則它們不在差異中，并且兩個索引都可以以 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 (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);uj5u.com熱心網友回復：
評論 trincot 的演算法。
它作業正常嗎？看起來，對 a 或 b 陣列的越界訪問存在風險。為了檢查它，我將演算法移植到 C 。它適用于演示資料。但是當我切換 a 和 b 的資料內容時（所以 a 變成了舊的 b，b 變成了舊的 a），我確實得到了一個越??界例外。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/490965.html
上一篇：Prim的演算法輸出為空