前言
面试手写代码在大厂面试中非常常见，秋招中面试小米就手写了一道flat实现的代码题，当时通过递归方式实现了数组扁平化逻辑，但没有考虑多种实现方案及其边界条件(主要是对所涉及到高阶函数的知识点不够熟练，也没有考虑空位处理)，现在从头梳理一下，并尽可能全面地总结数组扁平化的实现方案。
数组扁平化
数组扁平化即将一个嵌套多层的数组array(嵌套可以是任意层数)转换为只有一层的数组，如将数组[1,[2,[3,[4,5]]]]转换为[1,2,3,4,5]。
最直接的数组扁平化方案是使用Array.prototype.flat()方法(兼容性差)，其次是通过遍历数组元素递归实现每一层的数组拉平。
00x1 Array.prototype.flat()
按照一个可指定的深度递归遍历数组，并将所有元素与遍历到的子数组中的元素合并为一个新数组返回，对原数据没有影响。
语法：var newArray = arr.flat([depth])
说明：
代码示例：
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函数封装实现方案
实现思路
首先遍历获取数组的每一个元素，其次判断该元素类型是否为数组，最后将数组类型的元素展开一层。同时递归遍历获取该数组的每个元素进行拉平处理。
遍历数组方案
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));
判断数组元素是否为数组
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
注：
const str = ‘abc‘; str.constructor = Array; str.constructor === Array // true
数组元素展开一层方案
不推荐使用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 对空位的处理，大多数情况下会忽略空位。
ES6 明确将空位转为 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: "对象" }]
## 总结
现在的前端面试中，大厂面试官基本都会考察手撕代码的能力，不仅要能答得上来实现数组扁平化的几种方案，也不仅是要能手写实现，还要能理解，能讲清楚其中包涵的详细知识点及代码的边界情况，能在基础版本上再写出一个更完美的版本。
而我们在写代码的过程中，也要养成这样的习惯，多问问自己还有没有别的替代实现方案，还能不能进一步优化，才能写出优美漂亮的代码，编程能力自然而然也就提高啦！
原文：https://www.cnblogs.com/lynn-z/p/13915539.html