首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >不使用递归的多个嵌套数组的展平数组- javascript

不使用递归的多个嵌套数组的展平数组- javascript
EN

Stack Overflow用户
提问于 2014-12-05 04:26:14
回答 7查看 5K关注 0票数 4

也许这是一个愚蠢的问题,但我不知道可以在没有递归的情况下扁平化多维数组

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

代码语言:javascript
复制
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;
}

要展平的数组示例:

代码语言:javascript
复制
[1, {a: [2, 3]}, 4, [5, [6]], [[7], 8, 9], 10]

和执行:

代码语言:javascript
复制
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]

谢谢!

EN

回答 7

Stack Overflow用户

回答已采纳

发布于 2016-05-21 09:10:12

您可以使用堆栈。当您发现一个嵌套数组时,只需将其替换为它的项。

代码语言:javascript
复制
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;
}
票数 5
EN

Stack Overflow用户

发布于 2016-09-21 04:16:25

我在面试中提出了完全相同的问题,并提出了以下解决方案:

代码语言:javascript
复制
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)。

票数 4
EN

Stack Overflow用户

发布于 2018-06-26 06:03:39

这里是O(N)解决方案,其中N是扁平化数组中的项数,而不会改变输入数组。

在我看来,当我们使用stack时,使用pop和push更自然。此解决方案不使用非常昂贵的拼接、取消移位、移位和其他就地数组变异方法。

使用ES6扩展运算符,虽然不是必须的,但可以用apply代替。

代码语言:javascript
复制
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();
}
票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/27303369

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档