如何在javascript中展平嵌套数组?

IT技术 javascript arrays
2021-02-02 19:42:27

众所周知,要[[0, 1], [2, 3], [4, 5]]使用以下方法展平数组reduce()

var flattened = [[0, 1], [2, 3], [4, 5]].reduce(function(a, b) {
  return a.concat(b);
});

因此,如何扁平化这个数组[[[0], [1]], [[2], [3]], [[4], [5]]][0, 1, 2, 3, 4, 5]

6个回答

递归的完美用例,它可以处理更深的结构:

function flatten(ary) {
    var ret = [];
    for(var i = 0; i < ary.length; i++) {
        if(Array.isArray(ary[i])) {
            ret = ret.concat(flatten(ary[i]));
        } else {
            ret.push(ary[i]);
        }
    }
    return ret;
}

flatten([[[[[0]], [1]], [[[2], [3]]], [[4], [5]]]]) // [0, 1, 2, 3, 4, 5]

或者,作为 Array 方法:

Array.prototype.flatten = function() {
    var ret = [];
    for(var i = 0; i < this.length; i++) {
        if(Array.isArray(this[i])) {
            ret = ret.concat(this[i].flatten());
        } else {
            ret.push(this[i]);
        }
    }
    return ret;
};

[[[[[0]], [1]], [[[2], [3]]], [[4], [5]]]].flatten() // [0, 1, 2, 3, 4, 5]

编辑#1:好吧,认为它有点功能性的方式(命名递归除外,它应该使用 Y-combinator 进行纯功能性:D)。

function flatten(ary) {
  return ary.reduce(function(a, b) {
    if (Array.isArray(b)) {
      return a.concat(flatten(b))
    }
    return a.concat(b)
  }, [])
}

让我们采用一些 ES6 语法,使其更短,在一行中。

const flatten = (ary) => ary.reduce((a, b) => a.concat(Array.isArray(b) ? flatten(b) : b), [])

但请记住,这个不能作为数组方法应用,因为箭头函数没有自己的this.


编辑 #2:根据最新的Array.prototype.flat提案,这非常容易。数组方法接受一个可选参数depth,该参数指定嵌套数组结构应展平的深度(默认为1)。

[[[[[0]], [1]], [[[2], [3]]], [[4], [5]]]].flat()  // [[[[0]], [1]], [[[2], [3]]], [[4], [5]]]
[[[[[0]], [1]], [[[2], [3]]], [[4], [5]]]].flat(2) // [[[0]], [1], [[2], [3]], [4], [5]]
[[[[[0]], [1]], [[[2], [3]]], [[4], [5]]]].flat(3) // [[0], 1, [2], [3], 4, 5]
[[[[[0]], [1]], [[[2], [3]]], [[4], [5]]]].flat(4) // [0, 1, 2, 3, 4, 5]

因此,要展平任意深度的数组,只需flat使用Infinity.

[[[[[0]], [1]], [[[2], [3]]], [[4], [5]]]].flat(Infinity) // [0, 1, 2, 3, 4, 5]
这不是n^2吗?concat不是恒定时间操作。这是一个 O(n) 操作 AFAIK。
2021-04-06 19:42:27
这可以通过重用ret数组来加快一点有关此类解决方案,请参阅我的答案。
2021-04-08 19:42:27

ES6 风格的递归:

Redacted

2018 年 6 月更新:

现在有一个关于Array.prototype.flat方法的 ES 提议它目前处于第 3 阶段,这意味着它很可能很快就会被浏览器实现(ish)并以当前的形式将其纳入规范。可能有一些 polyfill 漂浮在周围。

例子:

const nested = [[[0], [1]], [[2], [3]], [[4], [5]]];
const flattened = nested.flat(2);  // Need to specify depth if > 1

2019 年 6 月更新:

Array.prototype.flat 在 ES2019 规范中正式添加到该语言中。

正如另一个答案所暗示的那样,是否有任何缺点以无穷大调用此方法?我们并不总是知道数组的深度。
2021-03-23 19:42:27
ES6 的良好实践
2021-03-30 19:42:27

这是递归的替代方法(请参阅此处的 jsfiddle),并且应该接受避免堆栈溢出的任何深度级别。

var array = [[0, 1], [2, 3], [4, 5, [6, 7, [8, [9, 10]]]]];
console.log(flatten(array), array); // does not mutate array
console.log(flatten(array, true), array); // array is now empty

// This is done in a linear time O(n) without recursion
// memory complexity is O(1) or O(n) if mutable param is set to false
function flatten(array, mutable) {
    var toString = Object.prototype.toString;
    var arrayTypeStr = '[object Array]';
    
    var result = [];
    var nodes = (mutable && array) || array.slice();
    var node;

    if (!array.length) {
        return result;
    }

    node = nodes.pop();
    
    do {
        if (toString.call(node) === arrayTypeStr) {
            nodes.push.apply(nodes, node);
        } else {
            result.push(node);
        }
    } while (nodes.length && (node = nodes.pop()) !== undefined);

    result.reverse(); // we reverse result to restore the original order
    return result;
}

你为什么使用Object.prototype.toString.call(node) == '[object Array]'而不是Array.isArray(node)
2021-03-24 19:42:27
为什么不使用 instanceof 运算符而不是 toString?if (node instanceof Array) { nodes.push.apply(nodes, node); } else { result.push(node); }
2021-03-27 19:42:27
偷偷摸摸地使用 apply 在那里拆分 arr,喜欢它。
2021-03-30 19:42:27
你也可以这样做,是的。此时的口味问题
2021-03-30 19:42:27
仅适用于 ie8 及以下
2021-04-03 19:42:27

ES2019 解决方案

ary.flat(Infinity);

而已。就这么简单。Infinity如果您愿意,您可以更改为适当的扁平度级别。

例子:

其他适用于以下旧浏览器的更长的解决方案


基于@Leo 的解决方案,但通过重用相同的数组并防止速度更快 .concat

function flatten(ary, ret = []) {
    for (const entry of ary) {
        if (Array.isArray(entry) {
            flatten(entry, ret);
        } else {
            ret.push(entry);
        }
    }
    return ret;
}
console.log(flatten([[[0], [1]], [[2], [3]], [[4], [5]]]));

或者使用Array.prototype.reduce,因为你提到了它:

function flatten(ary, ret = []) {
    return ary.reduce((ret, entry) => {
        if (Array.isArray(entry)) {
            flatten(entry, ret);
        } else {
            ret.push(entry);
        }
        return ret;
    }, ret);
}
console.log(flatten([[[0], [1]], [[2], [3]], [[4], [5]]]));

比这里的大多数答案要好得多。所有临时数组都在其他答案周围浮动,根本没有充分的理由。
2021-03-22 19:42:27
这仍然比接受的答案慢。
2021-03-28 19:42:27
@baltusaj 渐近分析对于这种特定情况几乎没有用,因为这个问题中的所有解决方案都遵循基本相同的算法。这是关于将这个解决方案与其他解决方案区分开来的常数项(比如创建一个空数组)。
2021-04-03 19:42:27
可能是这里最好和最易读的解决方案
2021-04-10 19:42:27
@timothygu 你能解释一下你将如何用 Big-O 表示法描述两种解决方案的时间和空间复杂性吗?
2021-04-11 19:42:27

ES6 单线:

function flatten(a) {
    return Array.isArray(a) ? [].concat(...a.map(flatten)) : a;
}

此外,非常深的数组的非递归版本(效率不高但相当优雅)

function flatten(a) {
    var queue = a.slice();
    var result = [];
    while(queue.length) {
        let curr = queue.pop();
        if(Array.isArray(curr)) {
            queue.push(...curr);
        }
        else result.push(curr);
    }
    return result;
}
更多 es6 魔法:让 flatten = a => Array.isArray(a) ? [].concat(...a.map(flatten)) : a;
2021-03-24 19:42:27
第二个实现没有通过我的测试
2021-04-01 19:42:27
@baltusaj 这是一个递归解决方案。如果当前元素不是数组,则返回它。如果是,则展平数组的每个元素(使用 Array.map),然后连接结果数组(使用 Array.concat 并将数组扩展到函数参数)
2021-04-03 19:42:27
谢谢。我猜“传播”是由三个点完成的。
2021-04-04 19:42:27
你的 ES6 one-liner 看起来很不错,但你能解释一下它是如何工作的吗?
2021-04-06 19:42:27