背景

最近，在編寫測試時，遇到了一些問題。我們?yōu)榱烁綦x對redis的依賴，在測試中，使用了ioredis-mock這個庫來代替 ioredis。 但是 ioredis-mock 的 hscan 行為與 ioredis的hscan行為不一致，導致我們測試無法跑過。為了解決這個問題，我們在 ioredis-mock 包裝層，基于ioredis-mock已有方法實現(xiàn)了 hscan 方法。在實現(xiàn) hscan 方法中，我們遇到了一個有趣的算法問題，如何將兩個數(shù)組交錯合并為一個新數(shù)組。

ioredis hscan 返回值
['cursor', ['filed1', 'value1', 'field2', 'value2']]

ioredis-mock hscan 返回值
['cursor', ['filed1', 'filed2']]

問題描述

合并兩個數(shù)組，使數(shù)組中的項交替出現(xiàn)。如下例所示：

var array1 = [1,2,3,4,5];
var array2 = ['a', 'b', 'c', 'd', 'e'];

// 期望的結(jié)果
var arrayCombined = [1, 'a', 2, 'b', 3, 'c', 4, 'd', 5, 'e'];

方法

方法一：迭代

const array1 = [1, 2, 3, 4, 5];
const array2 = ['a', 'b', 'c', 'd', 'e'];

const arrayCombined = array1.map((v, i) => [v, array2[i]])
    .reduce((a, b) => a.concat(b));

// [1, "a", 2, "b", 3, "c", 4, "d", 5, "e"]
console.log(arrayCombined);

// 優(yōu)化：將 2 次遍歷優(yōu)化為 1 次遍歷
var arrayCombined = array1.reduce(function(arr, v, i) {
    return arr.concat(v, array2[i]); 
}, []);

// [1, "a", 2, "b", 3, "c", 4, "d", 5, "e"]
console.log(arrayCombined);

思路：

1. 遍歷數(shù)組1，得到嵌套數(shù)組結(jié)構(gòu) [[1, 'a'], [2, 'b'], [3, 'c'], [4, 'd'], [5, 'e']]
2. 展開步驟1的結(jié)果，得到目標結(jié)果 [1, "a", 2, "b", 3, "c", 4, "d", 5, "e"]

對于步驟二，還可以使用 ECMAScript 2019 原生 flat 方法：

// 使用 ECMAScript 2019 flat 方法，扁平化數(shù)組
const arrayCombined = array1.map((v, i) => [v, array2[i]])
    .flat();

方法二：遞歸

const interleave = ([x, ...xs], ys = []) =>
    x === undefined
        ? ys
        : [x, ...interleave(ys, xs)];

為了解析這個算法，我們先看一個例子

// 入?yún)?const array1 = [1];
const array2 = ['a'];

const arrayCombined = interleave(array1, array2);

下表為 interleave 算法在本例的執(zhí)行情況：

需要注意兩個地方：

1. 算法在遞歸調(diào)用時，交替了參數(shù)的位置，如代碼所示，interleave(ys, xs)
2. interleave 執(zhí)行的結(jié)果，進行了解構(gòu)。[x, ...interleave(ys, xs)]

遞歸算法的核心思想:

• 階段一：分治，將復雜的大問題，分解成一個個小問題
  • interleave 算法中，將元素交錯的問題交給了遞歸解決
• 階段二：回歸分治任務(wù)，處理小問題的邊界情況與遞歸的截止條件
  • 通過判斷 x === undefined , 來處理是否終止遞歸

參考資料

• MDN - Array.prototype.flat()
• Merge Two Arrays so that the Values Alternate