背景
最近，在编写测试时，遇到了一些问题。我们为了隔离对redis的依赖，在测试中，使用了ioredis-mock这个库来代替 ioredis。 但是 ioredis-mock 的 hscan 行为与 ioredis的hscan行为不一致，导致我们测试无法跑过。为了解决这个问题，我们在 ioredis-mock 包装层，基于ioredis-mock已有方法实现了 hscan 方法。在实现 hscan 方法中，我们遇到了一个有趣的算法问题，如何将两个数组交错合并为一个新数组。
ioredis hscan 返回值
['cursor', ['filed1', 'value1', 'field2', 'value2']]
ioredis-mock hscan 返回值
['cursor', ['filed1', 'filed2']]
问题描述
合并两个数组，使数组中的项交替出现。如下例所示：
var array1 = [1,2,3,4,5];
var array2 = ['a', 'b', 'c', 'd', 'e'];
// 期望的结果
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);
// 优化：将 2 次遍历优化为 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，得到嵌套数组结构
[[1, 'a'], [2, 'b'], [3, 'c'], [4, 'd'], [5, 'e']] - 展开步骤1的结果，得到目标结果
[1, "a", 2, "b", 3, "c", 4, "d", 5, "e"]
对于步骤二，还可以使用 ECMAScript 2019 原生 flat 方法：
// 使用 ECMAScript 2019 flat 方法，扁平化数组
const arrayCombined = array1.map((v, i) => [v, array2[i]])
.flat();
方法二：递归
const interleave = ([x, ...xs], ys = []) =>
x === undefined
? ys
: [x, ...interleave(ys, xs)];
为了解析这个算法，我们先看一个例子
// 入参
const array1 = [1];
const array2 = ['a'];
const arrayCombined = interleave(array1, array2);
下表为 interleave 算法在本例的执行情况：
| 迭代次数 | x | xs | ys | result |
|---|---|---|---|---|
| 1 | 1 | undefined | ['a'] | [1, ...interleave(['a'], undefined)] |
| 2 | 'a' | undefined | [] | [1, 'a', ...interleave([], undefined)] |
| 3 | undefined | undefined | [] | [1, 'a', ...[]] |
需要注意两个地方：
- 算法在递归调用时，交替了参数的位置，如代码所示，
interleave(ys, xs) - interleave 执行的结果，进行了解构。
[x, ...interleave(ys, xs)]
递归算法的核心思想:
- 阶段一：分治，将复杂的大问题，分解成一个个小问题
- interleave 算法中，将元素交错的问题交给了递归解决
- 阶段二：回归分治任务，处理小问题的边界情况与递归的截止条件
- 通过判断
x === undefined, 来处理是否终止递归
- 通过判断
网友评论