Lynn_z

Lynn_z

关注
发信
关注(28)粉丝(399)

一文搞定数组扁平化（超全面的数组拉平方案及实现）

前言

面试手写代码在大厂面试中非常常见，秋招中面试小米就手写了一道flat实现的代码题，当时通过递归方式实现了数组扁平化逻辑，但没有考虑多种实现方案及其边界条件(主要是对所涉及到高阶函数的知识点不够熟练，也没有考虑空位处理)，现在从头梳理一下，并尽可能全面地总结数组扁平化的实现方案。

数组扁平化

数组扁平化即将一个嵌套多层的数组array(嵌套可以是任意层数)转换为只有一层的数组，如将数组[1,[2,[3,[4,5]]]]转换为[1,2,3,4,5]。

最直接的数组扁平化方案是使用Array.prototype.flat()方法(兼容性差)，其次是通过遍历数组元素递归实现每一层的数组拉平。

00x1 Array.prototype.flat()

按照一个可指定的深度递归遍历数组，并将所有元素与遍历到的子数组中的元素合并为一个新数组返回，对原数据没有影响。

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

说明：

  • depth为指定要提取嵌套数组的结构深度，默认值为1。
  • 参数depth值 <=0 时返回原数组；
  • 参数depth为Infinity 关键字时，无论多少层嵌套，都会转为一维数组，
  • flat()方法会移除数组中的空项，即原数组有空位，会跳过这个空位。

代码示例：

var arr1 = [1, 2, [3, 4]];
arr1.flat();
// [1, 2, 3, 4]

var arr2 = [1, 2, [3, 4, [5, 6]]];
arr2.flat();
// [1, 2, 3, 4, [5, 6]]

var arr3 = [1, 2, [3, 4, [5, 6]]];
arr3.flat(2);
// [1, 2, 3, 4, 5, 6]

//使用 Infinity，可展开任意深度的嵌套数组
var arr4 = [1, 2, [3, 4, [5, 6, [7, 8, [9, 10]]]]];
arr4.flat(Infinity);
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

var arr5 = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]];
arr5.flat(Infinity);
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { type: "对象" }];

// 移除数组中的空项
var arr6 = [1, 2, , 4, 5];
arr6.flat();
// [1, 2, 4, 5]

数组扁平化flat函数封装实现方案

实现思路
首先遍历获取数组的每一个元素，其次判断该元素类型是否为数组，最后将数组类型的元素展开一层。同时递归遍历获取该数组的每个元素进行拉平处理。
遍历数组方案

  • for循环
  • for...of
  • for...in
  • entries()
  • keys()
  • values()
  • forEach()
  • map()
  • reduce()
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]];
// 本文只枚举常用的几种数组遍历方法
// for 循环
for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}
// for...of
for (let value of arr) {
  console.log(value);
}
// for...in
for (let i in arr) {
  console.log(arr[i]);
}
// forEach 循环
arr.forEach(value => {
  console.log(value);
});
// entries（）
for (let [index, value] of arr.entries()) {
  console.log(value);
}
// keys()
for (let index of arr.keys()) {
  console.log(arr[index]);
}
// values()
for (let value of arr.values()) {
  console.log(value);
}
// reduce()
arr.reduce((pre, cur) => {
  console.log(cur);
}, []);
// map()
arr.map(value => console.log(value));

判断数组元素是否为数组

  • instanceof
  • constructor
  • Object.prototype.toString
  • isArray
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]];
arr instanceof Array
// true
arr.constructor === Array
// true
Object.prototype.toString.call(arr) === '[object Array]'
// true
Array.isArray(arr)
// true

注：

  • instanceof 操作符是假定只有一种全局环境，如果网页中包含多个框架，多个全局环境，如果你从一个框架向另一个框架传入一个数组，那么传入的数组与在第二个框架中原生创建的数组分别具有各自不同的构造函数。(所以在这种情况下会不准确)
  • typeof 操作符对数组取类型将返回 object
  • constructor可以被重写，不能确保一定是数组
const str = 'abc';
str.constructor = Array;
str.constructor === Array
// true

数组元素展开一层方案

  • 扩展运算符 + concat
  • concat +appl
  • toString + split

不推荐使用toString+split方法，操作字符串是很危险的，数组中元素都是数字时可行。

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]];
// 扩展运算符 + concat
[].concat(...arr)
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { type: "对象" }];

// concat + apply
[].concat.apply([], arr);
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { name: "对象" }];

// toString + split
const arr2 =[1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]]]
arr2.toString().split(',').map(v=>parseInt(v))
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3]

00x1 手写一个最简单的flat函数实现
这里使用ES6语法中的箭头函数定义函数，注意箭头函数没有arguments，caller，callee，同时要区分于ES5使用function的两种函数声明定义方式。

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]];
const flat = (arr) => {
  let arrResult = []
  for(let i=0, len=arr.length; i<len; i++){
    if(Array.isArray(arr[i])){
      arrResult.push(...flat(arr[i]))
      // arrResult = arrResult.concat(flat(arr[i]))
    }else{
      arrResult.push(arr[i])
    }
  }
  return arrResult;
}
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { type: "对象" }]


循环部分同理可用for...of / for...in 来实现。
OK，现在你已经具备了基本的手撕代码能力，但面试官常常希望你能掌握各种高阶函数方法的应用。接下来继续列举实现flat的几种方案。

00x2 用map/forEach实现flat函数
仍然是遍历+循环的原理，这里循环用map/forEach实现。

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]];
const flat = (arr) => {
  let arrResult = []
  arr.map(item => {
    if(Array.isArray(item)){
      arrResult.push(...flat(item))
      // arrResult = arrResult.concat(flat(item))
    }else{
      arrResult.push(item)
    }
  })
  return arrResult;
}
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { type: "对象" }]

00x3 归并方法：用reduce实现flat函数
我们用reduce函数进行遍历，把prev的初值赋值为[]，如果当前的值是数组的话，那么我们就递归遍历它的孩子，如果当前的值不是数组，那么我们就把它拼接进数组里。

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]];
function flat(arr) {
  return arr.reduce((prev, cur)=>{
    return prev.concat(Array.isArray(cur)?flat(cur):cur);
  }, [])
}
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { type: "对象" }]

00x4 用Generator实现flat函数

function* flat(arr, num) {
  if (num === undefined) num = 1;
  for (const item of arr) {
    if (Array.isArray(item) && num > 0) {   // num > 0
      yield* flat(item, num - 1);
    } else {
      yield item;
    }
  }
}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]]
// 调用 Generator 函数后，该函数并不执行，返回的也不是函数运行结果，而是一个指向内部状态的指针对象。
// 也就是遍历器对象（Iterator Object）。所以我们要用一次扩展运算符得到结果
[...flat(arr, Infinity)]
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { type: "对象" }]

00x5 在原型链上重写 flat 函数

Array.prototype.fakeFlat = function(num = 1) {
  if (!Number(num) || Number(num) < 0) {
    return this;
  }
  let arr = this.concat();    // 获得调用 fakeFlat 函数的数组
  while (num > 0) {
    if (arr.some(x => Array.isArray(x))) {
      arr = [].concat.apply([], arr);    // 数组中还有数组元素的话并且 num > 0，继续展开一层数组 
    } else {
      break; // 数组中没有数组元素并且不管 num 是否依旧大于 0，停止循环。
    }
    num--;
  }
  return arr;
};
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["type", { name: "对象" }]]
arr.fakeFlat(Infinity)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { type: "对象" }]

00x6 使用栈的思想实现 flat 函数

// 栈思想
function flat(arr) {
  const result = [];
  const stack = [].concat(arr);  // 将数组元素拷贝至栈，直接赋值会改变原数组
  //如果栈不为空，则循环遍历
  while (stack.length !== 0) {
    const val = stack.pop();
    if (Array.isArray(val)) {
      stack.push(...val); //如果是数组再次入栈，并且展开了一层
    } else {
      result.unshift(val); //如果不是数组就将其取出来放入结果数组中
    }
  }
  return result;
}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]]
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { type: "对象" }]

00x7 通过传入整数参数控制“拉平”层数

// reduce + 递归
function flat(arr, num = 1) {
  return num > 0
    ? arr.reduce(
        (pre, cur) =>
          pre.concat(Array.isArray(cur) ? flat(cur, num - 1) : cur),
        []
      )
    : arr.slice();
}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]]
flat(arr, Infinity);
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { type: "对象" }]

00x8 数组空位的处理
flat 函数执行是会跳过空位的。

ES5 对空位的处理，大多数情况下会忽略空位。

  • forEach(), filter(), reduce(), every() 和 some() 都会跳过空位。
  • map() 会跳过空位，但会保留这个值。
  • join() 和 toString() 会将空位视为 undefined，而 undefined 和 null 会被处理成空字符串。

ES6 明确将空位转为 undefined。

  • entries()、keys()、values()、find()和 findIndex() 会将空位处理成 undefined。
  • for...of 循环会遍历空位。
  • fill() 会将空位视为正常的数组位置。
  • copyWithin() 会连空位一起拷贝。
  • 扩展运算符（...）也会将空位转为 undefined。、
  • Array.from 方法会将数组的空位，转为 undefined。

00x1 for...of 循环遍历实现flat函数

const arr1 = [1, 2, 3, , , 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, ["string", { type: "对象" }]];
const flat = (arr) => {
  let arrResult = []
  for(let item of arr){
    if(Array.isArray(item)){
      arrResult.push(...flat(item))
      // arrResult = arrResult.concat(flat(arr[i]))
    }else{
      arrResult.push(item)
    }
  } return arrResult;
}
flat(arr1)
// [1, 2, 3, undefined, undefined, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { type: "对象" }]

## 总结
现在的前端面试中，大厂面试官基本都会考察手撕代码的能力，不仅要能答得上来实现数组扁平化的几种方案，也不仅是要能手写实现，还要能理解，能讲清楚其中包涵的详细知识点及代码的边界情况，能在基础版本上再写出一个更完美的版本。

而我们在写代码的过程中，也要养成这样的习惯，多问问自己还有没有别的替代实现方案，还能不能进一步优化，才能写出优美漂亮的代码，编程能力自然而然也就提高啦！

11-03 00:11
Powered by LMLPHP ©2024 Lynn_z 0.071732