高階前端面試手寫扁平資料結構轉Tree

2022-06-13 22:00:40

前言

招聘季節一般都在金三銀四，或者金九銀十。最近在這五六月份，陸陸續續面試了十幾個高階前端。有一套考察演演算法的小題目。後臺返回一個扁平的資料結構，轉成樹。

我們看下題目：打平的資料內容如下：

let arr = [
    {id: 1, name: '部門1', pid: 0},
    {id: 2, name: '部門2', pid: 1},
    {id: 3, name: '部門3', pid: 1},
    {id: 4, name: '部門4', pid: 3},
    {id: 5, name: '部門5', pid: 4},
]

輸出結果

[
{
"id": 1,
"name": "部門1",
"pid": 0,
"children": [
{
"id": 2,
"name": "部門2",
"pid": 1,
"children": []
},
{
"id": 3,
"name": "部門3",
"pid": 1,
"children": [
// 結果 ,,,
]
}
]
}
]

我們的要求很簡單，可以先不用考慮效能問題。實現功能即可，回頭分析了面試的情況，結果使我大吃一驚。

10%的人沒思路，沒碰到過這種結構

60%的人說用過遞迴，有思路，給他個筆電，但就是寫不出來

20%的人在引導下，磕磕絆絆能寫出來

剩下10%的人能寫出來，但效能不是最佳

感覺不是在招聘季節遇到一個合適的人真的很難。

接下來，我們用幾種方法來實現這個小演演算法

什麼是好演演算法，什麼是壞演演算法

判斷一個演演算法的好壞，一般從執行時間和佔用空間來看,執行時間越短，佔用的記憶體空間越小，那麼它就是好的演演算法。對應的，我們常常用時間複雜度代表執行時間，空間複雜度代表佔用的記憶體空間。

時間複雜度

時間複雜度的計算並不是計算程式具體執行的時間，而是演演算法執行語句的次數。

隨著n的不斷增大，時間複雜度不斷增大，演演算法花費時間越多。常見的時間複雜度有

常數階O(1)
對數階O(log2 n)
線性階O(n)
線性對數階O(n log2 n)
平方階O(n^2)
立方階O(n^3)
k次方階O(n^K)
指數階O(2^n)

計算方法

選取相對增長最高的項
最高項係數是都化為1
若是常數的話用O(1)表示

舉個例子：如f(n)=3*n^4+3n+300 則 O(n)=n^4

通常我們計算時間複雜度都是計算最壞情況。計算時間複雜度的要注意的幾個點

如果演演算法的執行時間不隨n的增加而增長，假如演演算法中有上千條語句，執行時間也不過是一個較大的常數。此類演演算法的時間複雜度是O(1)。舉例如下：程式碼執行100次，是一個常數，複雜度也是O(1)。

    let x = 1;
    while (x <100) {
     x++;
    }

有多個迴圈語句時候，演演算法的時間複雜度是由巢狀層數最多的迴圈語句中最內層語句的方法決定的。舉例如下：在下面for迴圈當中，外層迴圈每執行一次，內層迴圈要執行n次，執行次數是根據n所決定的，時間複雜度是O(n^2)。

  for (i = 0; i < n; i++){
         for (j = 0; j < n; j++) {
             // ...code
         }
     }

迴圈不僅與n有關，還與執行迴圈判斷條件有關。舉例如下：在程式碼中，如果arr[i]不等於1的話，時間複雜度是O(n)。如果arr[i]等於1的話，迴圈不執行，時間複雜度是O(0)。

    for(var i = 0; i<n && arr[i] !=1; i++) {
    // ...code
    }

空間複雜度

空間複雜度是對一個演演算法在執行過程中臨時佔用儲存空間的大小。

計算方法：

忽略常數，用O(1)表示
遞迴演演算法的空間複雜度=(遞迴深度n)*(每次遞迴所要的輔助空間)

計算空間複雜度的簡單幾點

僅僅只複製單個變數，空間複雜度為O(1)。舉例如下：空間複雜度為O(n) = O(1)。

   let a = 1;
   let b = 2;
   let c = 3;
   console.log('輸出a,b,c', a, b, c);

遞迴實現，呼叫fun函數，每次都建立1個變數k。呼叫n次，空間複雜度O(n*1) = O(n)。

    function fun(n) {
       let k = 10;
       if (n == k) {
           return n;
       } else {
           return fun(++n)
       }
    }

不考慮效能實現，遞迴遍歷查詢

主要思路是提供一個遞getChildren的方法，該方法遞回去查詢子集。就這樣，不用考慮效能，無腦去查，大多數人只知道遞迴，就是寫不出來。。。

/**
 * 遞迴查詢，獲取children
 */
const getChildren = (data, result, pid) => {
  for (const item of data) {
    if (item.pid === pid) {
      const newItem = {...item, children: []};
      result.push(newItem);
      getChildren(data, newItem.children, item.id);
    }
  }
}
/**
* 轉換方法
*/
const arrayToTree = (data, pid) => {
  const result = [];
  getChildren(data, result, pid)
  return result;
}

從上面的程式碼我們分析，該實現的時間複雜度為O(2^n)。

不用遞迴，也能搞定

主要思路是先把資料轉成Map去儲存，之後遍歷的同時藉助物件的參照，直接從Map找對應的資料做儲存

function arrayToTree(items) {
  const result = [];   // 存放結果集
  const itemMap = {};  // 
  // 先轉成map儲存
  for (const item of items) {
    itemMap[item.id] = {...item, children: []}
  }
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    const treeItem =  itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }
  }
  return result;
}

從上面的程式碼我們分析，有兩次迴圈，該實現的時間複雜度為O(2n)，需要一個Map把資料儲存起來，空間複雜度O(n)

最優效能

主要思路也是先把資料轉成Map去儲存，之後遍歷的同時藉助物件的參照，直接從Map找對應的資料做儲存。不同點在遍歷的時候即做Map儲存,有找對應關係。效能會更好。

function arrayToTree(items) {
  const result = [];   // 存放結果集
  const itemMap = {};  // 
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    if (!itemMap[id]) {
      itemMap[id] = {
        children: [],
      }
    }
    itemMap[id] = {
      ...item,
      children: itemMap[id]['children']
    }
    const treeItem =  itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }
  }
  return result;
}

從上面的程式碼我們分析，一次迴圈就搞定了，該實現的時間複雜度為O(n)，需要一個Map把資料儲存起來，空間複雜度O(n)

小試牛刀

方法	1000(條)	10000(條）	20000(條）	50000(條)
遞迴實現	154.596ms	1.678s	7.152s	75.412s
不用遞迴，兩次遍歷	0.793ms	16.499ms	45.581ms	97.373ms
不用遞迴，一次遍歷	0.639ms	6.397ms	25.436ms	44.719ms