面試官：JavaScript如何實現數組拍平（扁平化）方法?

面試官：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 數組空位處理

事實上我們應該盡量避免出現數組空位的情況

前面我們提到了遍曆數組的不同方法，它們對於數組空位的處理不盡相同

其中forEach、reduce、map遍歷時遇到空位會直接忽略；而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方法遍歷

當然也可以使用forEach、map方法來遍曆數組，這樣就不用手動判斷了

但是這裡有一個特殊情況需要考慮，就是當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;
}
Tags:

VirMach 便宜 VPS

QNews

QNews