数组扁平化 (Steamroller)

题目链接

• 中文链接
• 英文链接

问题解释

• 这个 function 接受一个数组参数 arr，返回值为扁平化之后的数组
• 如果 arr 是 [1, [2], [[3]]]，那么返回值应为 [1, 2, 3]
• 值得注意的是，如果存在空数组，那我们不应保留，如果存在空的 Object，那我们需要保留。比如，当 arr 是 [1, [], {}] 时，返回值应为 [1, {}]

解题思路

• 这道题目的要求看起来很简单，但思路上会有一点复杂。因此我们先来分析一下这道题目的思路
• 我们先来考虑一下什么是扁平化。在流程的控制上，其实只存在 “读取值” 以及 “深入 n 步” 两种可能。比如，当遇到 1，那我们就需要 “读取值”，或者说把这个值放到结果中；如果遇到 [1]，那我们就需要 “深入一步”，这样才能读取到 1，因为 [1] 是不应该出现在结果中的。同理，[[1]] 只需要 “深入两步” 就可以了
• 第一种情况很好实现。但对于第二种情况，我们来举几个例子，写一下伪代码，这样会帮助理解：

1
2
3
4

[1, 2, 3] 的处理过程：

for 循环:
    得到 1, 2, 3

1
2
3
4
5
6
7
8

[1, [2, 3], [4, 5]] 的处理过程：

for 循环:
    得到 1
    for 循环 [2, 3]:
        得到 2, 3
    for 循环 [4, 5]:
        得到 4, 5

1
2
3
4
5
6
7
8

[1, [2, 3, [4, 5]]] 的处理过程：

for 循环:
    得到 1
    for 循环 [2, 3, [4, 5]]:
        得到 2, 3
        for 循环 [4, 5]:
            得到 4, 5

• 以上三种情况，分别是深度为 1、2 以及 3 的例子。实际情况可能还会更复杂，而且我们无法提前知道深度。因为深度还有可能是 4、8。如果你想不清楚第二种和第三种的区别，请试着自己再举几个例子。请一定要先理解上面的内容，再开始写代码
• 另外，记得要处理特殊情况：
  • 对于空对象 {}，我们需要得到 {}
  • 对于空数组 []，则不应出现在结果中

基本解法 - 递归

思路提示

• 我们先来封装一下上面提到的递归逻辑。需要封装的逻辑大致是这样：
  • 判断传入的是否为数组：
    • 如果不是，直接添加到结果中
    • 如果为空数组，直接跳过
    • 如果为非空数组，那就递归调用这个函数，继续判断
  • 其次，我们需要先建立一个空数组用于保存结果，以便最终返回
  • 我们再来考虑一下参数设置成几个比较合适。如果这个变量位于我们封装的函数外，那么我们就需要在封装函数中修改外面的结果，也就是把扁平化之后的元素 push 到结果数组中。因此，参数方面我们只要传入一个就可以了，实际参数可能是数字、对象或者数组
• 记得以前说过，写递归的时候应该先考虑好跳出条件。这道题目中不难，可以先思考一下
• 那我们先开看看，如果把变量放到封装的函数外，应该如何写

代码 - 逻辑封装

1
2
3
4
5
6
7
8

var result = [];
function helper(arg) {
    if (!Array.isArray(arg)) {
        result.push(arg)
    } else {
        return arg.map(helper);
    }
}

解释

• 上面提到，既然是一个参数，那么我们需要在函数外部建立一个变量，用于存储最终的结果
• 从根源上来说，”对每一个元素都执行操作” 就是深入了一层。数组的方法中，map 方法可以针对每一个元素都执行操作。其实 forEach 方法也行，但 forEach 本身是没有返回值的，而 map 返回操作之后的数组。这也是我想到用 map 的原因
• 在这个函数中，处理的思路是：
  • 如果传入的参数不是数组，那么就把它添加到结果中
  • 如果传入的参数是数组，那么就对这个数组中的每一个元素都再执行一遍 helper 方法
• 注意，上面提到的第二条十分重要，这是这个递归的核心逻辑
  • 如果我们传入的 arg 是 [1, 2]，那我们就分别对 1 和 2 调用一次 helper，这时候就会给 result 添加上 1 和 2。这也就是我们上面说的 “深入一步” 的情景
  • 如果我们传入的 arg 是 [1, [2, 3]]，我们还是要分别对 1 和 [2, 3] 调用一次 helper，这时候就会给 result 添加上 1。但由于后面的 [2, 3] 是一个数组，因此不会直接添加。而是走到了 else 里，再对 [2, 3] 中的 2 和 3 调用一次 helper，然后才会把 2 和 3 添加到 result。这也就是我们上面说的 “深入两步” 的情景
• 因此，哪怕我们有再深的嵌套也不用担心了。因为只有不是 Array 的时候才会 push，是 Array 就会继续 map 往里找

代码 - 题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function steamroller(arr) {
    var result = [];

    function helper(arg) {
        if (!Array.isArray(arg)) {
            result.push(arg);
        } else {
            return arg.map(helper);
        }
    }
    
    helper(arr);
    
    return result;
}

另一种思路 - reduce 与 递归

思路提示

• 只要你理解了上面说的内容，而且对 reduce 这个方法有基本的理解，那写出来这个答案应该也是不难的
• Array.reduce 这个方法很有意思，它本身就是一个迭代器。我们只要给它设置对的返回值，就可以实现递归
• steamroller 函数本身只接受一个数组参数，我们是不可能给它多加一个参数的。虽然我们可以用 arguments 来读取到多传入的参数，但个人并不是很推荐

参考链接

• Array.reduce
• Array.concat

代码

1
2
3
4
5

function steamroller(arr) {
    return arr.reduce(function(accum, next) {
        return accum.concat(Array.isArray(next) ? steamroller(next) : next);
    }, []);
}

解释

• 其实和上面的思路基本一致。只是我们省去了创建 result、创建 helper、调用 helper 以及手动返回 result
• 简单理一下这个思路。accum 就是我们的结果数组。会一直帮我们保存结果。当 next 不是数组的时候，我们可以直接 concat 进结果数组；如果 next 是数组，那我们就把这个数组传入 steamroller 再进行后续计算。计算完成后，这个结果也会在弹出的过程中添加到 accum
• 顺便说一下，为什么这里要采用 concat 而不是 push。主要原因在于，push 方法的返回值为数组长度，而不是操作后的数组。相比之下，concat 返回值就是操作后的数组
• 但另一点很重要的区别在于 concat 可以接受单个元素、多个元素、单个数组甚至多个数组作为参数，这一点比 push 要灵活更多。可以试试这段代码，输出的均为一维数组

1
2
3
4

[1, 2].concat(3);
[1, 2].concat(3, 4);
[1, 2].concat([3]);
[1, 2].concat([3], [4, 5]);