問題

Array.prototype.flat() 可以用來扁平陣列，可以參考 MDN - Array.prototype.flat() 或是 lodash - _.flat()。

function flat(arr: Array<any>, depth: number): Array<any>

其主要參數有兩個：

1. arr：要扁平化的陣列。
2. depth：指定要扁平化的深度，預設為 1。

範例

const arr = [1, 2, [3, 4, [5, [6]]]]

flat(arr) // [1, 2, 3, 4, [5, [6]]]
flat(arr, 2) // [1, 2, 3, 4, 5, [6]]
flat(arr, Infinity) // [1, 2, 3, 4, 5, 6]

練習區

在了解問題後，可以嘗試先寫下您的思路，再到下方的練習區域實際寫出程式碼。

import { add } from './add';

describe('add', () => {
  test('Commutative Law of Addition', () => {
    expect(add(1, 2)).toBe(add(2, 1));
  });
});

追問

1. 如果你是用遞迴 (Recursion) 的方式來實踐，那是否可以也用迭代 (Iteration) 的方式來實踐？ 反之。

筆者思路

遞迴 (Recursion)

1. 定義基本情況 (base case)，如果深度小於等於 0 或者 arr 不是陣列。
2. 迭代陣列中的每個項目 (item)。
3. 如果項目是一個陣列且深度大於 0，那麼調用 flat(item, depth - 1) 。
4. 否則，我們將項目直接放入新陣列中。

迭代 (Iteration)

迭代的方式基本上就是模擬遞迴的行為，我們可以使用一個堆疊 (Stack) 來存放每個項目和深度，然後不斷地從堆疊中取出項目，直到堆疊為空。

1. 初始化堆疊：堆疊應該包含整個陣列及其初始深度。
2. 透過迴圈不斷地從堆疊中取出項目，直到堆疊為空。
3. 如果項目是一個陣列且深度大於 0，那麼將陣列中的每個項目都放入堆疊中。
4. 否則，將項目放入結果陣列中。

筆者解答

遞迴 (Recursion)

程式碼

function flat(arr, depth = 1) {
  // 1
  if (depth <= 0 || !Array.isArray(arr)) {
    return arr
  }

  const result = []

  arr.forEach((item) => {
    // 2
    if (Array.isArray(item) && depth > 0) {
      result.push(...flat(item, depth - 1)) // 3
    } else {
      result.push(item) // 4
    }
  })

  return result
}

進一步優化：可以看到上面有 result 跟 forEach 可以透過 reduce 改寫成更簡潔的方式：

function flat(arr, depth = 1) {
  if (depth <= 0 || !Array.isArray(arr)) {
    return arr
  }

  return arr.reduce((result, item) => {
    if (Array.isArray(item) && depth > 0) {
      result.push(...flat(item, depth - 1))
    } else {
      result.push(item)
    }
    return result
  }, [])
}

視覺化

可以想像成遞迴就是不斷地堆疊 (Stack)，每次調用 flat 函式就是將一個新的函式放入堆疊中，直到達到基本情況 (base case) 時，開始從堆疊中取出函式並執行。

flat([1, 2, [3, 4, [5, [6]]]], 2)
  flat([3, 4, [5, [6]]], 1)
    flat([5, [6]], 0)
      [5, [6]]
    [5, 6]
  [3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

複雜度

• 時間複雜度：O(n * d)

最壞情況下，如果所有的項目都是陣列並且需要展平到最大深度 d，則遞歸的總次數為 d，而每次遞歸中，遍歷陣列項目的數量為 n，每個元素可能還包含 m 個子元素。

• 空間複雜度：O(n + d)

遞歸的深度為 d，而每次遞歸中，都會創建一個新的陣列來存放結果，且每個陣列中可能包含 n 個元素。故總空間複雜度為 O(n \+ d)。

迭代 (Iteration)

程式碼

function flat(arr, depth = 1) {
  const stack = arr.map((item) => [item, depth])
  let result = []

  while (stack.length > 0) {
    const [item, d] = stack.pop()

    if (Array.isArray(item) && d > 0) {
      stack.push(...item.map((subItem) => [subItem, d - 1]))
    } else {
      result.unshift(item)
    }
  }

  return result
}

視覺化

flat([1, 2, [3, 4, [5, [6]]]], 2)
  stack: [[1, 2], [2, 2], [[3, 4, [5, [6]]], 2]]
  stack: [[1, 2], [2, 2], [3, 1], [4, 1], [[5, [6]], 1]]
  stack: [[1, 2], [2, 2], [3, 1], [4, 1], [5, 0], [[6], 0]]
  stack: [[1, 2], [2, 2], [3, 1], [4, 1], [5, 0], [6, 0]]
result: [1, 2, 3, 4, 5, 6]

相關題目

1. bigfrontend.dev - flat