面试官:JavaScript如何实现数组拍平(扁平化)方法?

  • A+
所属分类:Web前端
摘要

概念很简单,意思是将一个“多维”数组降维,比如:数组拍平也称数组扁平化、数组降维。


面试官: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 数组空位处理

事实上我们应该尽量避免出现数组空位的情况

前面我们提到了遍历数组的不同方法,它们对于数组空位的处理不尽相同

其中forEachreducemap遍历时遇到空位会直接忽略;而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方法遍历

当然也可以使用forEachmap方法来遍历数组,这样就不用手动判断了

但是这里有一个特殊情况需要考虑,就是当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; }