扁平化多个嵌套数组而无需递归-javascript

Question

也许这是一个愚蠢的问题，但我无法意识到是否有可能在不递归的情况下展平多维数组？

我有一个递归写的解决方案：

function transform (arr) {
   var result = [];
   arr.forEach(flatten)
   function flatten (el) {
     if (Array.isArray(el)) {
        return el.forEach(flatten);
     }
     return result.push(el);
   }
   return result;
}

要展平的数组的示例：

[1, {a: [2, 3]}, 4, [5, [6]], [[7], 8, 9], 10]

并执行：

var a = [1, {a: [2, 3]}, 4, [5, [6]], [[7], 8, 9], 10];
var r = transform(r);
console.log(r); // [1, {a: [2, 3]}, 4, 5, 6, 7, 8, 9, 10]

谢谢！

Answer 1

您可以使用堆栈。当您发现嵌套数组时，只需将其替换为其项目即可。

function flatten(arr) {
  var result = [];
  var stack = arr, first;

  while (stack.length > 0) {
    first = stack[0];

    if (Array.isArray(first)) {
      // Replace the nested array with its items
      Array.prototype.splice.apply(stack, [0, 1].concat(first));
    } else {
      result.push(first);
      // Delete the first item
      stack.splice(0, 1);
    }
  }

  return result;
}

Answer 2

我在面试中遇到了完全相同的问题，并提出了这个解决方案：

function flattenNonRecursion(arr) {
  const res = arr.slice();
  let i = 0;

  while (i < res.length) {
    if (Array.isArray(res[i])) {
      res.splice(i, 1, ...res[i]);
    }
    else {
      i++;
    }
  }

  return res;
}

console.log(flattenNonRecursion([1, {a: [2, 3]}, 4, [5, [6]], [[7], 8, 9], 10]));
// [1, {a: [2, 3]}, 4, 5, 6, 7, 8, 9, 10]

因此，主要思想是我们在数组中前进，如果遇到一个数组，我们用它的内容替换它并继续前进......这个解决方案的复杂度是 O(n)。

Answer 3

这里是 O(N) 解决方案，其中 N 是展平数组中的项目数，而不改变输入数组。

当我们使用堆栈时，对我来说使用弹出和推送似乎更自然。该解决方案不使用非常昂贵的拼接、取消移位、移位和其他就地数组变异方法。

使用 ES6 扩展运算符，虽然不是必须的，但可以替换为apply.

function flat(input) {
  const stack = [...input];
  const res = [];
  while (stack.length) {
    // pop value from stack
    const next = stack.pop();
    if (Array.isArray(next)) {
      // push back array items, won't modify the original input
      stack.push(...next);
    } else {
      res.push(next);
    }
  }
  return res.reverse();
}