FreeCodeCamp 高級演算法題 - 數組的對稱差

01-29

題目鏈接

中文鏈接
英文鏈接

問題解釋

這個 function 接收一個參數 arg，其中包含至少兩個數組。返回值也為數組，即為給出數組的對稱差
如果 arg 是 [1, 2, 3] 和 [5, 1, 2, 4]，則返回值為 [3, 4, 5]

解題思路

建議先去了解一下對稱差的定義
根據定義，對於兩個數組來說，對稱差的意思就是：

要麼在第一個數組中，要麼在第二個數組中。換句話說，在第一個數組中排除在第二個數組的元素，然後在第二個數組中排除在第一個數組的元素
從另一個角度考慮，其實就是先把兩個數組中所有元素都合併成一個數組，然後排除掉既在第一個數組也在第二個數組的元素

對於多個數組的操作也不難理解。設 A、B 和 C 分別代表三個數組，設 sym() 為求對稱差的函數。那麼 sym(A, B, C) 就相當於 sym(sym(A, B), C)
需要注意的是，如果數組中有重複元素，那麼在結果中是要過濾的。舉個例子，如果傳入 [1, 1, 2] 和 [2, 3]，那麼結果應該是 [1, 3]
先來看看對於上面提到的兩種求對稱差的邏輯分別如何實現

參考鏈接

Array.concat
Array.filter
Array.indexOf

代碼 - 對稱差公共邏輯 - 思路一

function getSym(arr1, arr2) {n // 得到在第一個數組，但不在第二個數組中的元素n var result = arr1.filter(function(e) {n return arr2.indexOf(e) === -1;n });n // 得到在第二個數組，但不在第以個數組中的元素n result.concat(arr2.filter(function(e) {n return arr1.indexOf(e) === -1;n }))n n // 去重n return result.filter(function(e, i) {n return result.indexOf(e) === i;n })n}n

代碼 - 對稱差公共邏輯 - 思路二

function getSym(arr1, arr2) {n return arr1.concat(arr2)n .filter(function(e) {n // 排除既在第一個也在第二個數組中的元素n return !(arr1.indexOf(e) > -1 && arr2.indexOf(e) > -1);n })n .filter(function(e, i, arr) {n return arr.indexOf(e) === i;n })n}n

解釋

第一個思路應該不難理解。我們先把在 arr1 中但不在 arr2 中的元素直接作為初始值賦給 result。然後，把在 arr2 中但不在 arr1 中的元素添加到 result里。最後，去重
去重的寫法可能有點兒不好理解。原理是這樣，對於有相同元素的數組，Array.indexOf 總是返回重複元素中第一個元素的索引。filter 方法的回調函數，第一個參數是元素本身，第二個參數是當前的索引。通過判斷這個當前索引和 Array.indexOf 返回值是否相等 (相等即保留) 就可以實現去重
第二種寫法，注意到第二個 filter 方法的回調函數中，我們多設置了一個參數。如果沒有很多次鏈式調用，需要傳入第三個參數的情況不是很多，因為我們可以直接通過調用者的變數名去調用
注意，這裡我們不可以用 this。原因很簡單，因為任何匿名函數的 this 指向的都是全局對象，比如 window

初級解法 - filter，循環

思路提示

參數是兩個數組的情況很好解決，但參數還可能是多個數組。按照一開始的思路，我們要先對前兩個求一次 sym，再對計算結果 (當然，這個計算結果是一個一維數組) 和下一個數組再求一次 sym
其實這就符合遞歸的模型，因為我們不確定需要做同樣的操作多少次。當然，用循環也是肯定可以解的
我們在上面已經封裝好了求兩數組對稱差的代碼，只要把這部分應用到題目中就可以了

代碼

解釋

需要注意的是，既然我們會在 for 循環中調用 i+1，那麼，我們就不能用 arguments.length 作為跳出條件了，因為當 i 為 arguments.length - 1 的時候，i + 1 為 arguments.length。對於一個數組 arr，顯然 arr[arr.length] 是 undefined
類似地，如果我們需要在循環中調用 i - 1，那我們就要把初始值設置為 1，而不是 0。arr[-1] 雖然不會報錯，但它會訪問數組的最後一個元素，很可能會影響結果

中級解法 - reduce

思路提示

其實應該很多朋友已經反應過來了，上面的就是在 reduce。對於 for 循環那裡，我們可以這樣寫：

var result = arguments[0];nfor (var i = 1; i < arguments.length; i++) {n result = getSym(result, arguments[i]);n}n

這就不難看出，其實就是在迭代 result，且 result 具有初始值 arguments[0]

參考鏈接

Array.reduce

代碼

function sym(arg) {n var argArr = [].slice.call(arguments);n return argArr.reduce(function(accum, e) {n return accum.concat(e).filter(function(ele) {n return accum.indexOf(ele) === -1 || e.indexOf(ele) === -1n }).filter(function(e, i, arr) {n return arr.indexOf(e) === i;n });n });n}n

本文標題:FreeCodeCamp 高級演算法題 - 數組的對稱差
文章作者:S1ngS1ng