面試官連環追問:數組拍平(扁平化)flat方法實現

NO IMAGE

前言

前段時間秋招面嗶哩嗶哩的時候,面試官問:如何實現 flat 方法?當時手寫的並不完美,後來回盤複習,發現面試要求手寫數組拍平(扁平化) flat 方法的面試官不在少數。其中包括:拼多多、小米、美團、滴滴、shopee、有贊等。手寫 flat 方法是一道非常基礎的面試題,通常出現在筆試或者第一輪面試當中,主要考察基本的手寫代碼的能力。今天就從瞭解 flat 特性到實現 flat 再到接住面試官的連環追問重新學習一遍數組拍平(扁平化) flat 方法吧。

Github 戳我

一段代碼總結 Array.prototype.flat() 特性

注:數組拍平方法 Array.prototype.flat() 也叫數組扁平化、數組拉平、數組降維。 本文統一叫:數組拍平

const animals = ["🐷", ["🐶", "🐂"], ["🐎", ["🐑", ["🐲"]], "🐛"]];
// 不傳參數時,默認“拉平”一層
animals.flat();
// ["🐷", "🐶", "🐂", "🐎", ["🐑", ["🐲"]], "🐛"]
// 傳入一個整數參數,整數即“拉平”的層數
animals.flat(2);
// ["🐷", "🐶", "🐂", "🐎", "🐑", ["🐲"], "🐛"]
// Infinity 關鍵字作為參數時,無論多少層嵌套,都會轉為一維數組
animals.flat(Infinity);
// ["🐷", "🐶", "🐂", "🐎", "🐑", "🐲", "🐛"]
// 傳入 <=0 的整數將返回原數組,不“拉平”
animals.flat(0);
animals.flat(-10);
// ["🐷", ["🐶", "🐂"], ["🐎", ["🐑", ["🐲"]], "🐛"]];
// 如果原數組有空位,flat()方法會跳過空位。
["🐷", "🐶", "🐂", "🐎",,].flat();
// ["🐷", "🐶", "🐂", "🐎"]

Array.prototype.flat() 特性總結

  • Array.prototype.flat() 用於將嵌套的數組“拉平”,變成一維的數組。該方法返回一個新數組,對原數據沒有影響。
  • 不傳參數時,默認“拉平”一層,可以傳入一個整數,表示想要“拉平”的層數。
  • 傳入 <=0 的整數將返回原數組,不“拉平”
  • Infinity 關鍵字作為參數時,無論多少層嵌套,都會轉為一維數組
  • 如果原數組有空位,Array.prototype.flat() 會跳過空位。

面試官 N 連問

第一問:實現一個簡單的數組拍平 flat 函數

首先,我們將花一點篇幅來探討如何實現一個簡單的數組拍平 flat 函數,詳細介紹多種實現的方案,然後再嘗試接住面試官的連環追問。

實現思路

如何實現呢,思路非常簡單:實現一個有數組拍平功能的 flat 函數,我們要做的就是在數組中找到是數組類型的元素,然後將他們展開。這就是實現數組拍平 flat 方法的關鍵思路。

有了思路,我們就需要解決實現這個思路需要克服的困難:

  • 第一個要解決的就是遍歷數組的每一個元素;
  • 第二個要解決的就是判斷元素是否是數組;
  • 第三個要解決的就是將數組的元素展開一層;

遍歷數組的方案

遍歷數組並取得數組元素的方法非常之多,包括且不限於下面幾種

  • for 循環
  • for...of
  • for...in
  • forEach()
  • entries()
  • keys()
  • values()
  • reduce()
  • map()
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "彈鐵蛋同學" }];
// 遍歷數組的方法有太多,本文只枚舉常用的幾種
// 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", { name: "彈鐵蛋同學" }];
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() 方法用於合併兩個或多個數組,在拼接的過程中加上擴展運算符會展開一層數組。詳細見下面的代碼。

  • concat +apply

主要是利用 apply 在綁定作用域時,傳入的第二個參數是一個數組或者類數組對象,其中的數組元素將作為單獨的參數傳給 func 函數。也就是在調用 apply 函數的過程中,會將傳入的數組一個一個的傳入到要執行的函數中,也就是相當對數組進行了一層的展開。

  • toString + split

不推薦使用 toString + split 方法,因為操作字符串是和危險的事情,在上一文章中我做了一個操作字符串的案例還被許多小夥伴們批評了。如果數組中的元素所有都是數字的話,toString +split 是可行的,並且是一步搞定。

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "彈鐵蛋同學" }];
// 擴展運算符 + concat
[].concat(...arr)
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { name: "彈鐵蛋同學" }];
// 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]

總結完要解決的三大困難,那我們就可以非常輕鬆的實現一版數組拍平 flat 函數了。

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "彈鐵蛋同學" }];
// concat + 遞歸
function flat(arr) {
let arrResult = [];
arr.forEach(item => {
if (Array.isArray(item)) {
arrResult = arrResult.concat(arguments.callee(item));   // 遞歸
// 或者用擴展運算符
// arrResult.push(...arguments.callee(item));
} else {
arrResult.push(item);
}
});
return arrResult;
}
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "彈鐵蛋同學" }];

到這裡,恭喜你成功得到了面試官對你手撕代碼能力的基本認可🎉。但是面試官往往會不止於此,將繼續考察面試者的各種能力。

第二問:用 reduce 實現 flat 函數

我見過很多的面試官都很喜歡點名道姓的要面試者直接用 reduce 去實現 flat 函數。想知道為什麼?文章後半篇我們考慮數組空位的情況的時候就知道為啥了。其實思路也是一樣的。

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "彈鐵蛋同學" }]
// 首先使用 reduce 展開一層
arr.reduce((pre, cur) => pre.concat(cur), []);
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { name: "彈鐵蛋同學" }];
// 用 reduce 展開一層 + 遞歸
const flat = arr => {
return arr.reduce((pre, cur) => {
return pre.concat(Array.isArray(cur) ? flat(cur) : cur);
}, []);
};
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "彈鐵蛋同學" }];

第三問:使用棧的思想實現 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", { name: "彈鐵蛋同學" }]
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "彈鐵蛋同學" }];

第四問:通過傳入整數參數控制“拉平”層數

// 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", { name: "彈鐵蛋同學" }]
flat(arr, Infinity);
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "彈鐵蛋同學" }];

第五問:使用 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", { name: "彈鐵蛋同學" }]
// 調用 Generator 函數後,該函數並不執行,返回的也不是函數運行結果,而是一個指向內部狀態的指針對象。
// 也就是遍歷器對象(Iterator Object)。所以我們要用一次擴展運算符得到結果
[...flat(arr, Infinity)]    
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "彈鐵蛋同學" }];

第六問:實現在原型鏈上重寫 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, "string", { name: "彈鐵蛋同學" }]
arr.fakeFlat(Infinity)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "彈鐵蛋同學" }];

第七問:考慮數組空位的情況

由最開始我們總結的 flat 特性知道,flat 函數執行是會跳過空位的。ES5 大多數數組方法對空位的處理都會選擇跳過空位包括:forEach(), filter(), reduce(), every()some() 都會跳過空位。

所以我們可以利用上面幾種方法來實現 flat 跳過空位的特性

// reduce + 遞歸
Array.prototype.fakeFlat = function(num = 1) {
if (!Number(num) || Number(num) < 0) {
return this;
}
let arr = [].concat(this);
return num > 0
? arr.reduce(
(pre, cur) =>
pre.concat(Array.isArray(cur) ? cur.fakeFlat(--num) : cur),
[]
)
: arr.slice();
};
const arr = [1, [3, 4], , ,];
arr.fakeFlat()
// [1, 3, 4]
// foEach + 遞歸
Array.prototype.fakeFlat = function(num = 1) {
if (!Number(num) || Number(num) < 0) {
return this;
}
let arr = [];
this.forEach(item => {
if (Array.isArray(item)) {
arr = arr.concat(item.fakeFlat(--num));
} else {
arr.push(item);
}
});
return arr;
};
const arr = [1, [3, 4], , ,];
arr.fakeFlat()
// [1, 3, 4]

擴展閱讀:由於空位的處理規則非常不統一,所以建議避免出現空位。

ES5 對空位的處理,就非常不一致,大多數情況下會忽略空位。

  • forEach(), filter(), reduce(), every()some() 都會跳過空位。
  • map() 會跳過空位,但會保留這個值。
  • join()toString() 會將空位視為 undefined,而 undefinednull 會被處理成空字符串。

ES6 明確將空位轉為 undefined

  • entries()keys()values()find()findIndex() 會將空位處理成 undefined
  • for...of 循環會遍歷空位。
  • fill() 會將空位視為正常的數組位置。
  • copyWithin() 會連空位一起拷貝。
  • 擴展運算符(...)也會將空位轉為 undefined
  • Array.from 方法會將數組的空位,轉為 undefined

總結

面試官現場考察一道寫代碼的題目,其實不僅僅是寫代碼,在寫代碼的過程中會遇到各種各樣的知識點和代碼的邊界情況。雖然大多數情況下,面試官不會那麼變態,就 flat 實現去連續追問面試者,並且手撕好幾個版本,但面試官會要求在你寫的那版代碼的基礎上再寫出一個更完美的版本是常有的事情。只有我們沉下心來把基礎打紮實,不管面試官如何追問,我們都能自如的應對。flat 的實現絕對不會只有文中列出的這幾個版本,敲出自己的代碼是最好的進步,在評論區或者在 issue 中寫出你自己的版本吧!

Today i learned.如果你學到了就點波關注點個贊👍吧

文末彩蛋

記得兩個禮拜前的星期天,晚上十點左右,在掘金髮了自己第一遍技術博文。週一下午就收到了 70 多個贊,非常受寵若驚,心裡預期能有 70 個贊已經非常滿意了。可萬萬沒想到,5 天左右文章點贊上了 1000+,掘金等級直接上升到 3 級,被大家認可真的非常開心。那篇文章在某個方案中代碼寫的非常的糟糕,非常感謝在評論區指出我的錯誤小夥伴們,也非常感謝給我點讚的小夥伴們,真心感謝每小夥伴給的贊。同時也非常希望能夠和各位小夥伴成為學習和生活上的朋友,一起交流技術和生活。彈鐵蛋同學非常歡迎大家加我微信和加群聊天~彈鐵蛋同學也隨手開了個公眾號,主要記錄自己的技術文章和自己的生活感觸,同時還在網上收集了很多前端學習的資料都放在了公眾號裡,大家也可以隨手關注一波哦,也可以私聊我內推你哦~

面試官連環追問:數組拍平(扁平化)flat方法實現

推薦閱讀

你不知道的 JSON.stringify() 的威力

相關文章

圖解JavaScript對象—現代JavaScript教程

MySQL二進制日誌複製、GTID複製與半同步複製

談談魔法消失UI框架Svelte

如何解決高併發場景下緩存+數據庫雙寫不一致問題?