在Javascript中展平第n个嵌套数组的迭代解决方案

Question

任何人都可以向我展示以下问题的迭代解决方案吗？我递归地解决了它,但是在迭代解决方案上挣扎.(Facebook技术访谈问题)

Input: [1, {a: 2}, [3], [[4, 5], 6], 7]
Output: [1, {a: 2}, 3, 4, 5, 6, 7]

解决方案必须适用于第n个嵌套数组元素(即如果有人修改了上面示例中的数组值/位置,它仍然可以工作)

递归解决方案:

var flatten = function(input) {
    var result = [];

    input.forEach(function(element) {
        result = result.concat(Array.isArray(element) ? flatten(element) : element);
    });

    return result;
}

Answer 1

这是一种方式:

var input = [1, {a: 2}, [3], [[4, 5], 6], 7];
function flatten(input) {
    var i, placeHolder = [input], lastIndex = [-1], out = [];
    while (placeHolder.length) {
        input = placeHolder.pop();
        i = lastIndex.pop() + 1;
        for (; i < input.length; ++i) {
            if (Array.isArray(input[i])) {
                placeHolder.push(input);
                lastIndex.push(i);
                input = input[i];
                i = -1;
            } else out.push(input[i]);
        }
    }
    return out;
}
flatten(input);

说明:如果在嵌套结构上进行迭代,则只需要在移动到嵌套数组之前保存当前数组和位置,就必须记住以前的位置(这通常通过堆栈处理递归解决方案).

注意:如果重用数组placeHolder,lastIndex则不需要每次都重新创建它们.也许是这样的:

var flatten = function(){ 
    var placeHolder = [], lastIndex = [];
    placeHolder.count = 0;
    lastIndex.count = 0;
    return function flatten(input) {
        var i, out = [];
        placeHolder[0] = input; placeHolder.count = 1;
        lastIndex[0] = -1; lastIndex.count = 1;
        while (placeHolder.count) {
            input = placeHolder[--placeHolder.count];
            i = lastIndex[--lastIndex.count] + 1;
            for (; i < input.length; ++i) {
                if (Array.isArray(input[i])) {
                    placeHolder[placeHolder.count++] = input;
                    lastIndex[lastIndex.count++] = i;
                    input = input[i];
                    i = -1;
                } else out.push(input[i]);
            }
        }
        return out;
    }
}();

这甚至更快(对于平面迭代),并且更少的垃圾收集器问题多次调用它.速度非常接近Chrome中的递归函数调用速度,并且比FireFox和IE中的递归速度快很多倍.

我在这里重新创建了Tomalak的测试,因为旧的jsPerf已被打破以进行编辑:https://jsperf.com/iterative-array-flatten-2

Answer 2

这个怎么样？

inp = [1, {a: 2}, [3], [[4, 5], 6], 7]
out = inp;

while(out.some(Array.isArray))
  out = [].concat.apply([], out);

document.write(JSON.stringify(out));