面試官連環(huán)追問：數(shù)組拍平（扁平化） flat 方法實現(xiàn)

【轉(zhuǎn)載】原文地址：https://juejin.im/post/5dff18a4e51d455804256d31

前言

前段時間秋招面嗶哩嗶哩的時候互拾，面試官問：如何實現(xiàn) flat 方法惜浅？當(dāng)時手寫的并不完美篡诽，后來回盤復(fù)習(xí)贵涵，發(fā)現(xiàn)面試要求手寫數(shù)組拍平（扁平化） flat 方法的面試官不在少數(shù)厢呵。其中包括：拼多多从诲、小米果元、美團员萍、滴滴腾降、shopee、有贊等碎绎。手寫 flat 方法是一道非丑θ溃基礎(chǔ)的面試題，通常出現(xiàn)在筆試或者第一輪面試當(dāng)中筋帖，主要考察基本的手寫代碼的能力奸晴。今天就從了解 flat 特性到實現(xiàn) flat 再到接住面試官的連環(huán)追問重新學(xué)習(xí)一遍數(shù)組拍平（扁平化） flat 方法吧。

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

注：數(shù)組拍平方法Array.prototype.flat() 也叫數(shù)組扁平化日麸、數(shù)組拉平寄啼、數(shù)組降維。 本文統(tǒng)一叫：數(shù)組拍平

const animals = ["??", ["??", "??"], ["??", ["??", ["??"]], "??"]];

// 不傳參數(shù)時代箭，默認(rèn)“拉平”一層
animals.flat();
// ["??", "??", "??", "??", ["??", ["??"]], "??"]

// 傳入一個整數(shù)參數(shù)墩划，整數(shù)即“拉平”的層數(shù)
animals.flat(2);
// ["??", "??", "??", "??", "??", ["??"], "??"]

// Infinity 關(guān)鍵字作為參數(shù)時，無論多少層嵌套嗡综，都會轉(zhuǎn)為一維數(shù)組
animals.flat(Infinity);
// ["??", "??", "??", "??", "??", "??", "??"]

// 傳入 <=0 的整數(shù)將返回原數(shù)組乙帮，不“拉平”
animals.flat(0);
animals.flat(-10);
// ["??", ["??", "??"], ["??", ["??", ["??"]], "??"]];

// 如果原數(shù)組有空位，flat()方法會跳過空位蛤高。
["??", "??", "??", "??",,].flat();
// ["??", "??", "??", "??"]

Array.prototype.flat() 特性總結(jié)

Array.prototype.flat() 用于將嵌套的數(shù)組“拉平”蚣旱，變成一維的數(shù)組碑幅。該方法返回一個新數(shù)組，對原數(shù)據(jù)沒有影響塞绿。

不傳參數(shù)時沟涨，默認(rèn)“拉平”一層，可以傳入一個整數(shù)异吻，表示想要“拉平”的層數(shù)裹赴。

傳入<=0的整數(shù)將返回原數(shù)組，不“拉平”

Infinity 關(guān)鍵字作為參數(shù)時诀浪，無論多少層嵌套棋返，都會轉(zhuǎn)為一維數(shù)組

如果原數(shù)組有空位，Array.prototype.flat()會跳過空位雷猪。

面試官 N 連問

第一問：實現(xiàn)一個簡單的數(shù)組拍平 flat 函數(shù)

首先睛竣，我們將花一點篇幅來探討如何實現(xiàn)一個簡單的數(shù)組拍平 flat 函數(shù)，詳細(xì)介紹多種實現(xiàn)的方案求摇，然后再嘗試接住面試官的連環(huán)追問射沟。

實現(xiàn)思路

如何實現(xiàn)呢，思路非常簡單：實現(xiàn)一個有數(shù)組拍平功能的 flat函數(shù)与境，我們要做的就是在數(shù)組中找到是數(shù)組類型的元素验夯，然后將他們展開。這就是實現(xiàn)數(shù)組拍平 flat 方法的關(guān)鍵思路摔刁。

有了思路挥转，我們就需要解決實現(xiàn)這個思路需要克服的困難：

第一個要解決的就是遍歷數(shù)組的每一個元素；

第二個要解決的就是判斷元素是否是數(shù)組共屈；

第三個要解決的就是將數(shù)組的元素展開一層绑谣；

遍歷數(shù)組的方案

遍歷數(shù)組并取得數(shù)組元素的方法非常之多，包括且不限于下面幾種：

for 循環(huán)

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: "彈鐵蛋同學(xué)" }];
// 遍歷數(shù)組的方法有太多拗引，本文只枚舉常用的幾種
// for 循環(huán)
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 循環(huán)
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));

只要是能夠遍歷數(shù)組取到數(shù)組中每一個元素的方法域仇，都是一種可行的解決方案。

判斷元素是數(shù)組的方案

instanceof

constructor

Object.prototype.toString

isArray

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "彈鐵蛋同學(xué)" }];
arr instanceof Array
// true
arr.constructor === Array
// true
Object.prototype.toString.call(arr) === '[object Array]'
// true
Array.isArray(arr)
// true

說明：

instanceof 操作符是假定只有一種全局環(huán)境寺擂，如果網(wǎng)頁中包含多個框架，多個全局環(huán)境泼掠，如果你從一個框架向另一個框架傳入一個數(shù)組怔软，那么傳入的數(shù)組與在第二個框架中原生創(chuàng)建的數(shù)組分別具有各自不同的構(gòu)造函數(shù)。（所以在這種情況下會不準(zhǔn)確）

typeof操作符對數(shù)組取類型將返回 object

因為constructor 可以被重寫择镇，所以不能確保一定是數(shù)組挡逼。

const str = 'abc';
str.constructor = Array;
str.constructor === Array 
// true

將數(shù)組的元素展開一層的方案

擴展運算符 + concat

concat() 方法用于合并兩個或多個數(shù)組，在拼接的過程中加上擴展運算符會展開一層數(shù)組腻豌。詳細(xì)見下面的代碼家坎。

concat +apply

主要是利用apply 在綁定作用域時嘱能，傳入的第二個參數(shù)是一個數(shù)組或者類數(shù)組對象，其中的數(shù)組元素將作為單獨的參數(shù)傳給func 函數(shù)虱疏。也就是在調(diào)用apply 函數(shù)的過程中惹骂，會將傳入的數(shù)組一個一個的傳入到要執(zhí)行的函數(shù)中，也就是相當(dāng)對數(shù)組進行了一層的展開做瞪。

toString + split

不推薦使用 toString + split 方法对粪，因為操作字符串是和危險的事情，在上一文章中我做了一個操作字符串的案例還被許多小伙伴們批評了装蓬。如果數(shù)組中的元素所有都是數(shù)字的話著拭，toString +split 是可行的，并且是一步搞定牍帚。

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "彈鐵蛋同學(xué)" }];
// 擴展運算符 + concat
[].concat(...arr)
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { name: "彈鐵蛋同學(xué)" }];

// concat + apply
[].concat.apply([], arr);
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { name: "彈鐵蛋同學(xué)" }];

// 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]

總結(jié)完要解決的三大困難儡遮，那我們就可以非常輕松的實現(xiàn)一版數(shù)組拍平 flat 函數(shù)了。

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

到這里暗赶，恭喜你成功得到了面試官對你手撕代碼能力的基本認(rèn)可??鄙币。但是面試官往往會不止于此，將繼續(xù)考察面試者的各種能力忆首。

第二問：用 reduce 實現(xiàn)flat 函數(shù)

我見過很多的面試官都很喜歡點名道姓的要面試者直接用 reduce 去實現(xiàn) flat 函數(shù)爱榔。想知道為什么？文章后半篇我們考慮數(shù)組空位的情況的時候就知道為啥了糙及。其實思路也是一樣的详幽。

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "彈鐵蛋同學(xué)" }]

// 首先使用 reduce 展開一層
arr.reduce((pre, cur) => pre.concat(cur), []);
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { name: "彈鐵蛋同學(xué)" }];

// 用 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: "彈鐵蛋同學(xué)" }];

第三問：使用棧的思想實現(xiàn) flat 函數(shù)

// 棧思想
function flat(arr) {
  const result = []; 
  const stack = [].concat(arr);  // 將數(shù)組元素拷貝至棧，直接賦值會改變原數(shù)組
  //如果棧不為空浸锨，則循環(huán)遍歷
  while (stack.length !== 0) {
    const val = stack.pop(); 
    if (Array.isArray(val)) {
      stack.push(...val); //如果是數(shù)組再次入棧唇聘，并且展開了一層
    } else {
      result.unshift(val); //如果不是數(shù)組就將其取出來放入結(jié)果數(shù)組中
    }
  }
  return result;
}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "彈鐵蛋同學(xué)" }]
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "彈鐵蛋同學(xué)" }];

第四問：通過傳入整數(shù)參數(shù)控制“拉平”層數(shù)

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

第五問：使用 Generator 實現(xiàn) flat 函數(shù)

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: "彈鐵蛋同學(xué)" }]
// 調(diào)用 Generator 函數(shù)后，該函數(shù)并不執(zhí)行柱搜，返回的也不是函數(shù)運行結(jié)果迟郎，而是一個指向內(nèi)部狀態(tài)的指針對象。
// 也就是遍歷器對象（Iterator Object）聪蘸。所以我們要用一次擴展運算符得到結(jié)果
[...flat(arr, Infinity)]    
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "彈鐵蛋同學(xué)" }];

第六問：實現(xiàn)在原型鏈上重寫 flat 函數(shù)

Array.prototype.fakeFlat = function(num = 1) {
  if (!Number(num) || Number(num) < 0) {
    return this;
  }
  let arr = this.concat();    // 獲得調(diào)用 fakeFlat 函數(shù)的數(shù)組
  while (num > 0) {           
    if (arr.some(x => Array.isArray(x))) {
      arr = [].concat.apply([], arr);   // 數(shù)組中還有數(shù)組元素的話并且 num > 0宪肖，繼續(xù)展開一層數(shù)組 
    } else {
      break; // 數(shù)組中沒有數(shù)組元素并且不管 num 是否依舊大于 0，停止循環(huán)健爬。
    }
    num--;
  }
  return arr;
};
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "彈鐵蛋同學(xué)" }]
arr.fakeFlat(Infinity)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "彈鐵蛋同學(xué)" }];

第七問：考慮數(shù)組空位的情況

由最開始我們總結(jié)的flat 特性知道控乾，flat 函數(shù)執(zhí)行是會跳過空位的。ES5 大多數(shù)數(shù)組方法對空位的處理都會選擇跳過空位包括：forEach(),filter(), reduce(), every()和some() 都會跳過空位娜遵。

所以我們可以利用上面幾種方法來實現(xiàn) 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]

擴展閱讀：由于空位的處理規(guī)則非常不統(tǒng)一蜕衡，所以建議避免出現(xiàn)空位。

ES5 對空位的處理设拟，就非常不一致慨仿，大多數(shù)情況下會忽略空位久脯。

forEach(), filter(), reduce(), every() 和 some()都會跳過空位。

map()會跳過空位镰吆，但會保留這個值帘撰。

join() 和 toString() 會將空位視為 undefined，而 undefined 和 null 會被處理成空字符串鼎姊。

ES6 明確將空位轉(zhuǎn)為 undefined骡和。

entries()、keys()相寇、values()慰于、find()和 findIndex() 會將空位處理成 undefined。

for...of 循環(huán)會遍歷空位唤衫。

fill()會將空位視為正常的數(shù)組位置婆赠。

copyWithin()會連空位一起拷貝。

擴展運算符（...）也會將空位轉(zhuǎn)為 undefined佳励。

Array.from方法會將數(shù)組的空位休里，轉(zhuǎn)為undefined。

總結(jié)

面試官現(xiàn)場考察一道寫代碼的題目赃承，其實不僅僅是寫代碼妙黍，在寫代碼的過程中會遇到各種各樣的知識點和代碼的邊界情況。雖然大多數(shù)情況下瞧剖，面試官不會那么變態(tài)拭嫁，就 flat 實現(xiàn)去連續(xù)追問面試者，并且手撕好幾個版本抓于，但面試官會要求在你寫的那版代碼的基礎(chǔ)上再寫出一個更完美的版本是常有的事情做粤。只有我們沉下心來把基礎(chǔ)打扎實，不管面試官如何追問捉撮，我們都能自如的應(yīng)對怕品。flat 的實現(xiàn)絕對不會只有文中列出的這幾個版本，敲出自己的代碼是最好的進步

原文地址：https://juejin.im/post/5dff18a4e51d455804256d31

學(xué)習(xí)地址

image

END

image
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末巾遭，一起剝皮案震驚了整個濱河市肉康，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌灼舍，老刑警劉巖迎罗，帶你破解...
    沈念sama閱讀 206,602評論 6贊 481
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異片仿，居然都是意外死亡，警方通過查閱死者的電腦和手機尤辱，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,442評論 2贊 382
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門砂豌，熙熙樓的掌柜王于貴愁眉苦臉地迎上來厢岂，“玉大人，你說我怎么就攤上這事阳距∷＃” “怎么了？”我有些...
    開封第一講書人閱讀 152,878評論 0贊 344
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵筐摘，是天一觀的道長卒茬。 經(jīng)常有香客問我，道長咖熟，這世上最難降的妖魔是什么圃酵？ 我笑而不...
    開封第一講書人閱讀 55,306評論 1贊 279
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮馍管，結(jié)果婚禮上郭赐，老公的妹妹穿的比我還像新娘。我一直安慰自己确沸，他們只是感情好捌锭，可當(dāng)我...
    茶點故事閱讀 64,330評論 5贊 373
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布。 她就那樣靜靜地躺著罗捎，像睡著了一般观谦。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上桨菜，一...
    開封第一講書人閱讀 49,071評論 1贊 285
  • 城市分裂傳說
    那天豁状，我揣著相機與錄音，去河邊找鬼雷激。 笑死替蔬，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的屎暇。 我是一名探鬼主播承桥，決...
    沈念sama閱讀 38,382評論 3贊 400
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼根悼！你這毒婦竟也來了凶异？” 一聲冷哼從身側(cè)響起，我...
    開封第一講書人閱讀 37,006評論 0贊 259
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤挤巡，失蹤者是張志新（化名）和其女友劉穎剩彬，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體矿卑，經(jīng)...
    沈念sama閱讀 43,512評論 1贊 300
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡喉恋，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 35,965評論 2贊 325
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片轻黑。...
    茶點故事閱讀 38,094評論 1贊 333
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡糊肤，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出氓鄙，到底是詐尸還是另有隱情馆揉，我是刑警寧澤，帶...
    沈念sama閱讀 33,732評論 4贊 323
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布抖拦，位于F島的核電站升酣，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏态罪。R本人自食惡果不足惜噩茄，卻給世界環(huán)境...
    茶點故事閱讀 39,283評論 3贊 307
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望向臀。 院中可真熱鬧巢墅，春花似錦、人聲如沸券膀。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,286評論 0贊 19
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽芹彬。三九已至蓄髓，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間舒帮，已是汗流浹背会喝。 一陣腳步聲響...
    開封第一講書人閱讀 31,512評論 1贊 262
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留玩郊，地道東北人肢执。 一個月前我還...
    沈念sama閱讀 45,536評論 2贊 354
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像译红，于是被迫代替她去往敵國和親预茄。 傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 42,828評論 2贊 345