在Javascript中平滑第n个嵌套数组的迭代解决方案 [英] Iterative solution for flattening n-th nested arrays in Javascript

问题描述

任何人都可以为我解决以下问题的迭代解决方案吗？我递归地解决了这个问题，但是却遇到了一个迭代解决方案。 （Facebook技术面试问题）

 输入：[1，{a：2}，[3]，[[4，5 ]，6]，7] 
输出：[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）; 
}）; 
 
返回结果; 
 
  

解决方案

以下是一种方法： / p>

  var input = [1，{a：2}，[3]，[[4,5]，6]，7 ]。 
函数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]）; 
} 
} 
退出; 
} 
 flatten（input）; 
  

说明：如果遍历嵌套结构，则必须记住你可以在之前保存当前的数组和位置，然后再进入嵌套数组（这通常是通过栈来处理递归解决方案）。你重用数组 placeHolder 和 lastIndex ，你不需要每次都重新创建它们。也许是这样的：

  var flatten = function（）{
 var placeHolder = []，lastIndex = [] ; 
 placeHolder.count = 0; 
 lastIndex.count = 0; 
返回函数flatten（input）{
 var i，out = []; 
 placeHolder [0] =输入; 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]）; 
} 
} 
退出; 
} 
}（）; 
  

这再次更快（对于平面迭代），并且垃圾收集器问题更少倍。速度非常接近于Chrome中递归函数的调用速度，并且比FireFox和IE中的递归速度快很多倍。

我重新创建了Tomalak的测试，因为旧的jsPerf中断编辑： https://jsperf.com/iterative-array-flatten-2

Can anyone show me an iterative solution for the following problem? I solved it recursively but struggled with an iterative solution. (Facebook Technical Interview Question)

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

Solution must work with n-th nested array elements (i.e. it must still work if someone modifies the array values/placement in the example above)

Recursive solution:

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

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

    return result;
}

解决方案

Here is one way:

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);

Explanation: If iterating over a nested structure, you just have to remember where you were before by saving the current array and position before moving into the nested array (this is usually taken care of via the stack for recursive solutions).

Note: If you reuse the arrays placeHolder and lastIndex you won't need to keep recreating them every time. Perhaps something like this:

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;
    }
}();

This is even faster again (for flat iteration that is), and less garbage collector issues calling it many times. The speed is very close to that of recursive function calling in Chrome, and many times faster than recursion in FireFox and IE.

I recreated Tomalak's tests here since the old jsPerf is broken for editing: https://jsperf.com/iterative-array-flatten-2

这篇关于在Javascript中平滑第n个嵌套数组的迭代解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！