Symmetric Difference
创建一个函数，接受两个或多个数组，返回所给数组的 对等差分(symmetric difference) (△ or ⊕)数组. 给出两个集合 (如集合 A = {1, 2, 3} 和集合 B = {2, 3, 4}), 而数学术语 "对等差分" 的集合就是指由所有只在两个集合其中之一的元素组成的集合(A △ B = C = {1, 4}). 对于传入的额外集合 (如 D = {2, 3}), 你应该安装前面原则求前两个集合的结果与新集合的对等差分集合 (C △ D = {1, 4} △ {2, 3} = {1, 2, 3, 4}).
function sym(args) {
var result = [];
var filter = [];
for(var i=0;i<arguments.length;i++)
{
filter = distinct(arguments[i]);
pick(filter);
}
function distinct(arr)
{
arr.forEach(function(emt)
{
if(filter.indexOf(emt) === -1)
filter.push(emt);
});
return filter;
}
function pick(arr)
{
arr.forEach(function(emt)
{
if(result.indexOf(emt) == -1)
result.push(emt);
else
result[result.indexOf(emt)] = undefined;
});
filter = [];
}
return result.filter(function(emt){ return emt != null;});
}
sym([1, 2, 3], [5, 2, 1, 4]);
測試的正確結果
sym([1, 2, 3], [5, 2, 1, 4]) 应该返回 [3, 4, 5].sym([1, 2, 3], [5, 2, 1, 4]) 应该只包含三个元素.
sym([1, 2, 5], [2, 3, 5], [3, 4, 5]) 应该返回 [1, 4, 5]
sym([1, 2, 5], [2, 3, 5], [3, 4, 5]) 应该只包含三个元素.
sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]) 应该返回 [1, 4, 5].
sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]) 应该只包含三个元素.
sym([3, 3, 3, 2, 5], [2, 1, 5, 7], [3, 4, 6, 6], [1, 2, 3]) 应该返回 [2, 3, 4, 6, 7].
sym([3, 3, 3, 2, 5], [2, 1, 5, 7], [3, 4, 6, 6], [1, 2, 3]) 应该只包含五个元素.
sym([3, 3, 3, 2, 5], [2, 1, 5, 7], [3, 4, 6, 6], [1, 2, 3], [5, 3, 9, 8], [1]) 应该返回 [1, 2, 4, 5, 6, 7, 8, 9].
sym([3, 3, 3, 2, 5], [2, 1, 5, 7], [3, 4, 6, 6], [1, 2, 3], [5, 3, 9, 8], [1]) 应该只包含八个元素.
Solution:
對稱差是集合間的運算，兩個集合A和B，其對稱差AΔB有幾種等價的定義方式：
AΔB = (A - B)∪(B - A)
AΔB = (A∪B) - (A∩B)
而我們該怎麼做呢? 對稱差就是要找出2個陣列的不同之處，因為是好幾個陣列，且怕陣列本身有重複的元素，所以我寫了一個distinct函數，然後用distinct把每個array中重複的元素先去掉，作法就是設一個空的array - filter，然後訪問輸入陣列的每個元素，檢查是否出現在filter裡面，沒有就加進去，這樣一來就可以去除重複的元素，再來將每個array依序用pick函數和indexOf檢查result array裡面是否存在同樣的元素，一開始因為result這個array裡面沒有東西，所以第1輪元素會全部加進去result裡面，等到來到了第2輪遇到重複的元素的時候，會把result裡面重複的元素值設定成undefined，最後再將result裡面的undefined部分用array的filter過濾掉，就可以獲得對稱差的元素了，記得在pick函數裡面最後要將filter array清空，不然會殘留上一個array的元素值。
P.S. / Reference: Array.reduce()
Symmetric Difference
Wiki entry about Symmetric Difference