前言

招聘季節(jié)一般都在金三銀四，或者金九銀十。最近在這五六月份，陸陸續(xù)續(xù)面試了十幾個(gè)高級(jí)前端。有一套考察算法的小題目。后臺(tái)返回一個(gè)扁平的數(shù)據(jù)結(jié)構(gòu)，轉(zhuǎn)成樹。

我們看下題目：打平的數(shù)據(jù)內(nèi)容如下：

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},
]

輸出結(jié)果

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

我們的要求很簡(jiǎn)單，可以先不用考慮性能問題。實(shí)現(xiàn)功能即可，回頭分析了面試的情況，結(jié)果使我大吃一驚。

10%的人沒思路，沒碰到過這種結(jié)構(gòu)

60%的人說用過遞歸，有思路，給他個(gè)筆記本，但就是寫不出來

20%的人在引導(dǎo)下，磕磕絆絆能寫出來

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

感覺不是在招聘季節(jié)遇到一個(gè)合適的人真的很難。

接下來，我們用幾種方法來實(shí)現(xiàn)這個(gè)小算法

什么是好算法，什么是壞算法

判斷一個(gè)算法的好壞，一般從執(zhí)行時(shí)間和占用空間來看,執(zhí)行時(shí)間越短，占用的內(nèi)存空間越小，那么它就是好的算法。對(duì)應(yīng)的，我們常常用時(shí)間復(fù)雜度代表執(zhí)行時(shí)間，空間復(fù)雜度代表占用的內(nèi)存空間。

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度的計(jì)算并不是計(jì)算程序具體運(yùn)行的時(shí)間，而是算法執(zhí)行語句的次數(shù)。

隨著n的不斷增大，時(shí)間復(fù)雜度不斷增大，算法花費(fèi)時(shí)間越多。 常見的時(shí)間復(fù)雜度有

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

計(jì)算方法

• 選取相對(duì)增長(zhǎng)最高的項(xiàng)
• 最高項(xiàng)系數(shù)是都化為1
• 若是常數(shù)的話用O(1)表示

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

通常我們計(jì)算時(shí)間復(fù)雜度都是計(jì)算最壞情況。計(jì)算時(shí)間復(fù)雜度的要注意的幾個(gè)點(diǎn)

• 如果算法的執(zhí)行時(shí)間不隨n的增加而增長(zhǎng)，假如算法中有上千條語句，執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O(1)。 舉例如下：代碼執(zhí)行100次，是一個(gè)常數(shù)，復(fù)雜度也是O(1)。

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

• 有多個(gè)循環(huán)語句時(shí)候，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的方法決定的。舉例如下：在下面for循環(huán)當(dāng)中，外層循環(huán)每執(zhí)行一次，內(nèi)層循環(huán)要執(zhí)行n次，執(zhí)行次數(shù)是根據(jù)n所決定的，時(shí)間復(fù)雜度是O(n^2)。

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

• 循環(huán)不僅與n有關(guān)，還與執(zhí)行循環(huán)判斷條件有關(guān)。舉例如下：在代碼中，如果arr[i]不等于1的話，時(shí)間復(fù)雜度是O(n)。如果arr[i]等于1的話，循環(huán)不執(zhí)行，時(shí)間復(fù)雜度是O(0)。

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

空間復(fù)雜度

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間的大小。

計(jì)算方法：

• 忽略常數(shù)，用O(1)表示
• 遞歸算法的空間復(fù)雜度=(遞歸深度n)*(每次遞歸所要的輔助空間)

計(jì)算空間復(fù)雜度的簡(jiǎn)單幾點(diǎn)

僅僅只復(fù)制單個(gè)變量，空間復(fù)雜度為O(1)。舉例如下：空間復(fù)雜度為O(n) = O(1)。

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

遞歸實(shí)現(xiàn)，調(diào)用fun函數(shù)，每次都創(chuàng)建1個(gè)變量k。調(diào)用n次，空間復(fù)雜度O(n*1) = O(n)。

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

不考慮性能實(shí)現(xiàn)，遞歸遍歷查找

主要思路是提供一個(gè)遞getChildren的方法，該方法遞歸去查找子集。 就這樣，不用考慮性能，無腦去查，大多數(shù)人只知道遞歸，就是寫不出來。。。

/**
 * 遞歸查找，獲取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);
    }
  }
}
/**
* 轉(zhuǎn)換方法
*/
const arrayToTree = (data, pid) => {
  const result = [];
  getChildren(data, result, pid)
  return result;
}

從上面的代碼我們分析，該實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(2^n)。

不用遞歸，也能搞定

主要思路是先把數(shù)據(jù)轉(zhuǎn)成Map去存儲(chǔ)，之后遍歷的同時(shí)借助對(duì)象的引用，直接從Map找對(duì)應(yīng)的數(shù)據(jù)做存儲(chǔ)

function arrayToTree(items) {
  const result = [];   // 存放結(jié)果集
  const itemMap = {};  // 
  // 先轉(zhuǎn)成map存儲(chǔ)
  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;
}

從上面的代碼我們分析，有兩次循環(huán)，該實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(2n)，需要一個(gè)Map把數(shù)據(jù)存儲(chǔ)起來，空間復(fù)雜度O(n)

最優(yōu)性能

主要思路也是先把數(shù)據(jù)轉(zhuǎn)成Map去存儲(chǔ)，之后遍歷的同時(shí)借助對(duì)象的引用，直接從Map找對(duì)應(yīng)的數(shù)據(jù)做存儲(chǔ)。不同點(diǎn)在遍歷的時(shí)候即做Map存儲(chǔ),有找對(duì)應(yīng)關(guān)系。性能會(huì)更好。

function arrayToTree(items) {
  const result = [];   // 存放結(jié)果集
  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;
}

從上面的代碼我們分析，一次循環(huán)就搞定了，該實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(n)，需要一個(gè)Map把數(shù)據(jù)存儲(chǔ)起來，空間復(fù)雜度O(n)

小試牛刀

從我們的測(cè)試結(jié)果來看，隨著數(shù)量的增大，遞歸的實(shí)現(xiàn)會(huì)越來越慢，基本成指數(shù)的增長(zhǎng)方式。

以上就是高級(jí)前端面試手寫扁平數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)Tree的詳細(xì)內(nèi)容，更多關(guān)于扁平數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)Tree的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論