乐趣区

关于javascript:面试官JavaScript如何实现数组拍平扁平化方法

jiezi

面试官：JavaScript 如何实现数组拍平（扁平化）办法?

1 什么叫数组拍平？

概念很简略，意思是将一个“多维”数组降维，比方：

// 原数组是一个“三维”数组
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]

// 能够降成二维
newArray1 = [1, 2, 3, 4, [5, 6], 7, 8, 9]

// 也能够降成一维
newArray2 = [1, 2, 3, 4, 5, 6, 7, 8, 9]

数组拍平 也称数组扁平化、数组降维。

2 JS 规范库中的数组拍平办法

JavaScript规范库中曾经实现了数组拍平办法Array.prototype.flat()

flat() 办法会依照一个可指定的深度 递归遍历数组 ，并将所有元素与遍历到的子数组中的元素合并为一个 新数组 返回。

语法：var newArray = arr.flat([depth])

参数：depth为可选值，示意要遍历多维数组的深度，默认值为 1。能够了解为想要开展（或者说降维）的层数。

返回值：遍历到的元素和子数组的元素组合成的新数组

举例：

const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
const newArray1 = array.flat() // 等价于 array.flat(1)；降 1 维
// newArray1: [1, 2, 3, 4, [ 5, 6], 7, 8, 9]

const newArray2 = array.flat(2) // 降 2 维
// newArray2：[1, 2, 3, 4, 5, 6, 7, 8, 9]

非凡：

  1. depth<=0时，返回的数组和原数组维数一样（留神只是维数一样，空位状况见第 3 点）
const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
array.flat(-1)
// [1, 2, [3, 4, [5, 6], 7], 8, 9]
  1. depth=Infinity，返回的数组变成一维
array.flat(Infinity)
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
  1. 原数组有空位，flat 办法会打消空位，即便是 flat(0)也会打消空位，所以第 1 点说的是“只是维数一样”。并且 flat 办法开展到哪一层，空位就会打消到哪一层，再深层的空位不会打消
const array1 = [1, , 2, [3, ,4, [5, 6], 7], 8, 9] 
// 留神这个数组有两个空位
array.flat(0)
// [1, 2, [ 3,，4, [ 5, 6], 7 ], 8, 9 ]
// 第一个空位没了，第二个空位还在

3 实现一个 flat 办法

flat办法开展一层（降 1 维）的步骤：遍历数组，判断以后元素是否为数组，如果不是数组，间接保留；如果是数组，将其开展后保留

flat办法开展多层（降多维）无非就是在开展一层的根底上，应用 递归 将数组子元素进行同样的操作。

能够将这个办法拆分成三步：

1、如何遍历数组

2、如何判断元素是否为数组

3、递归

实现上述三步，将他们组合起来就能够失去不同的 flat 实现

3.1 如何遍历一个数组

办法特地多，这里介绍 3 类：

1、for相干

  • for 循环
  • for...of

for...in是为遍历对象属性而构建的，不倡议与数组一起应用

const array = [1, 2, [3, 4, [5, 6], 7], 8, 9]
// for 循环
for (let i = 0; i < array.length; i++) {const element = array[i];
}
// for...of
for (const element of array) {}

2、数组办法：能间接取到数组元素的办法

  • forEach()
  • reduce()
  • map()
// forEach()
array.forEach(element => {});
// reduce()
array.reduce((pre, cur) => {const element = cur}, [])
// map()
array.map(element => {})

3、数组办法：返回遍历器 (Iterator) 对象的办法

  • keys()
  • values()
  • entries()
// 这三种形式仅仅是取得遍历器对象，还需搭配 for...of 来进行遍历
// keys()
for (let i of array.keys()) {const element = array[i]
}
// values()
for (let element of array.values() ) { }
// entries()
for (let [i, element] of array.entries()) {console.log(array[i])
  console.log(element)
}

3.2 如何判断元素是否为数组

设有一变量a，判断其是否为数组。这里提供 4 种办法：

  • Array有一个静态方法 Array.isArray() 用于判断某个变量是否是一个数组

  • instanceof运算符用于检测构造函数的 prototype 属性是否呈现在某个实例对象的原型链上。

    若 a 是数组，则其原型链上会呈现Array.prototype

  • 通过对象的 constructor 判断（此办法可能生效，因为 constructor 能够手动更改）
  • 通过 Object.prototype.toString() 来判断，该办法能够返回一个示意该对象的字符串
// 办法 1
Array.isArray(a)
// 办法 2
a instanceof Array
// 办法 3
a.constructor === Array
// 办法 4
// 应用 call 来调用 Object.prototype 上的 toString 办法
Object.prototype.toString.call(a) === '[object Array]'

// 不能这么判断，因为这个 toString 曾经笼罩了 Object.prototype.toString
// 只有 Object.prototype.toString 能正确判断类型
a.toString()

3.3 递归

递归：对子元素进行同样的操作

function flat() {let res = []
  遍历数组 {if (以后元素是数组) {flat(以后元素)失去一维数组
      将一维数组拼接到 res 中
    } else {res.push(以后元素)
    }
  }
  return res
}

3.4 初步实现 flat 办法

筛选遍历形式和判断数组的形式，搭配递归就能够初步实现 flat 办法，如：

function myFlat(arr) {let res = [];
  for (const item of arr) {if (Array.isArray(item)) {res = res.concat(myFlat(item));
      // 留神 concat 办法返回一个新数组，不会扭转原数组
    } else {res.push(item);
    }
  }
  return res;
}

myFlat办法能够实现将 ” 多维 ” 数组拉平成一维数组，然而不能指定开展深度depth，并且也无奈解决数组空位

4 优化

4.1 指定开展深度

解决开展深度其实很简略，咱们能够增设一个递归终止条件，即depth<=0，代码如下：

function myFlat(arr, depth = 1) {
  // 若 depth<=0，则间接返回
  if (depth <= 0) {return arr}
  let res = [];
  for (const item of arr) {if (Array.isArray(item)) {
      // 每次递归调用，将 depth-1
      res = res.concat(myFlat(item, depth - 1));
    } else {res.push(item);
    }
  }
  return res;
}

4.2 数组空位解决

事实上咱们应该尽量避免呈现数组空位的状况

后面咱们提到了遍历数组的不同办法，它们对于数组空位的解决不尽相同

其中 forEach、reduce、map 遍历时遇到空位会间接疏忽；而 for...of 则不会 疏忽，它遇到空位会将其当作 undefined 解决

4.2.1 for…of 减少空位判断

因而咱们须要改良 for...of 遍历数组的 myFlat 办法：

function myFlat(arr, depth = 1) {if (depth <= 0) {return arr;}
  let res = [];
  for (const item of arr) {if (Array.isArray(item)) {res = res.concat(myFlat(item, depth - 1));
    } else {
      // 判断数组空位
      item !== undefined && res.push(item);
    }
  }
  return res;
}

4.2.2 forEach、map 办法遍历

当然也能够应用 forEach、map 办法来遍历数组，这样就不必手动判断了

然而这里有一个非凡状况须要思考，就是当 depth <= 0 时，咱们用 filter 办法来打消数组空位

// forEach
function myFlat(arr, depth = 1) {if (depth <= 0) {return arr.filter(item => item !== undefined);
  }
  let res = [];
  arr.forEach((item) => {if (Array.isArray(item)) {res = res.concat(myFlat(item, depth - 1));
    } else {res.push(item);
    }
  });
  return res;
}

// map
function myFlat(arr, depth = 1) {if (depth <= 0) {return arr.filter(item => item !== undefined);
  }
  let res = [];
  arr.map((item) => {if (Array.isArray(item)) {res = res.concat(myFlat(item, depth - 1));
    } else {res.push(item);
    }
  });
  return res;
}

4.2.3 reduce 办法

其中，应用 reduce 办法实现的最为简洁，也是面试中常考的办法之一

function myFlat(arr, depth = 1) {
  return depth > 0
    ? arr.reduce((pre, cur) =>
          pre.concat(Array.isArray(cur) ? myFlat(cur, depth - 1) : cur),
        [])
    : arr.filter((item) => item !== undefined);
}

5 其余

5.1 栈

实践上，递归办法通常能够转换成非递归办法，即应用 栈

function myFlat(arr) {let res = [];
  const stack = [].concat(arr);
  while (stack.length > 0) {const item = stack.pop();
    if (Array.isArray(item)) {
      // 用扩大运算符开展一层
      stack.push(...item);
    } else {item !== undefined && res.unshift(item);
    }
  }
  return res;
}

然而此办法 不能 指定开展深度，只能彻底开展成一维数组

5.2 改良

针对 栈不能指定开展深度的毛病进行改良，代码如下：

function myFlat(arr, depth = 1) {if (depth <= 0) {return arr.filter((item) => item !== undefined);
  }
  let res;
  let queue = [].concat(arr);
  while (depth > 0) {res = [];
    queue.forEach((item) => {if (Array.isArray(item)) {
        // 留神用扩大运算符将数组开展前先用 filter 办法去掉空位
        res.push(...item.filter((e) => e !== undefined));
      } else {res.push(item);
      }
    });
    depth--;
    queue = res;
  }
  return res;
}

公众号【前端嘛】

退出移动版