第 125 题：如何将 [{id: 1}, {id: 2, pId: 1}, ...] 的重复数组（有重复数据）转成树形结构的数组 [{id: 1, child: [{id: 2, pId: 1}]}, ...] （需要去重） #243

yygmind · 2019-08-13T01:55:37Z

No description provided.

ZodiacSyndicate · 2019-08-13T02:11:48Z

哈希表，时间复杂度O(n)

const fn = arr => {
  const res = []
  const map = arr.reduce((res, item) => ((res[item.id] = item), res), {})
  for (const item of Object.values(map)) {
    if (!item.pId) {
      res.push(item)
    } else {
      const parent = map[item.pId]
      parent.child = parent.child || []
      parent.child.push(item)
    }
  }
  return res
}

// const arr = [{id: 1}, {id:2, pId: 1}, {id: 3, pId: 2}, {id: 4}, {id:3, pId: 2}, {id: 5, pId: 4}]
// fn(arr) => [{id: 1, child: [{id: 2, pId: 1, child: [{ id: 3, pId: 2}]}]}, {id: 4, child: [{id: 5, pId: 4}]}]

weiweixuan · 2019-08-13T06:09:07Z

是这个意思吗，不太清楚，轻喷哈

 //    如何将 [{id: 1}, {id: 2, pId: 1}, ...] 的重复数组（有重复数据）转成树形结构的数组 [{id: 1, child: [{id: 2, pId: 1}]}, ...] （需要去重）
      let arr = [
        { id: 1 },
        { id: 2, pid: 1 },
        { id: 3, pid: 2 },
        { id: 4, pid: 1 },
        { id: 5, pid: 3 },
        { id: 6, pid: 2 },
        { id: 6, pid: 2 },
        { id: 2, pid: 1 }
      ]
      function changeSet(arr) {
        let flatArr = [...new Set(arr.map(item => JSON.stringify(item)))].map(
          item => JSON.parse(item)
        )
        let res = flatArr.reduce((prev, item) => {
          if (item.pid) {
            let father = flatArr.find(cur => cur.id == item.pid)
            father.child ? father.child.push(item) : (father.child = [item])
            return prev
          } else {
            return (item.child = []), prev.push(item), prev
          }
        }, [])
      }
      let res = changeSet(arr)
      console.log(res)

JaniceDong · 2019-08-13T06:19:17Z

var flatLs = [
{ id: 1},
{ id: 2},
{ id: 3},
{ id: 4, pid: 1 },
{ id: 5, pid: 3 },
{ id: 6, pid: 2 },
{ id: 7, pid: 4 },
{ id: 8, pid: 3 },
{ id: 9, pid: 4 }
]
const flat2tree = flatLs => {
flatLs.forEach(item => {
if (!item.pid) {
item.pid = 0;
} else {
const index = flatLs.findIndex(_item => _item.id === item.pid)
if (index !== -1) {
flatLs[index].children = flatLs[index].children || []
flatLs[index].children.push(item)
}
}
})
return flatLs.filter(item => item.pid === 0)
}
为什么代码没有缩进，[笑哭]

McCarthey · 2019-08-13T07:05:18Z

哈希表，时间复杂度O(n)

const fn = arr => {
  const res = []
  const map = arr.reduce((res, item) => ((res[item.id] = item), res), {})
  for (const item of Object.values(map)) {
    if (!item.pId) {
      res.push(item)
    } else {
      const parent = map[item.pId]
      parent.child = parent.child || []
      parent.child.push(item)
    }
  }
  return res
}

// const arr = [{id: 1}, {id:2, pId: 1}, {id: 3, pId: 2}, {id: 4}, {id:3, pId: 2}, {id: 5, pId: 4}]
// fn(arr) => [{id: 1, child: [{id: 2, pId: 1, child: [{ id: 3, pId: 2}]}]}, {id: 4, child: [{id: 5, pId: 4}]}]

@ZodiacSyndicate 👍 厉害！（提个小建议，最好复制一下对象，否则会修改原数组）

const map = arr.reduce((res, item) => ((res[item.id] = Object.assign({}, item)), res), {})

GitHubJiKe · 2019-08-13T08:43:42Z

const arr = [
  { id: 1, pid: null },
  { id: 2, pid: 1 },
  { id: 3, pid: 1 },
  { id: 4, pid: 2 },
  { id: 5, pid: 2 },
  { id: 6, pid: 3 },
  { id: 7, pid: 3 },
  { id: 8, pid: 3 },
  { id: 9, pid: 8 },
  { id: 10, pid: 6 }
];

function arr2tree(arr = []) {
  let rootNode = arr.find(v => v.pid === null);
  if (!rootNode) {
    throw new Error("Expected rootNode not exists");
  }
  let rootNodeIndex = arr.findIndex(v => v.pid === null);
  arr.splice(rootNodeIndex, 1);
  let tree = {
    id: rootNode.id,
    children: []
  };
  let map = {};
  arr.forEach(v => {
    if (!map[v.pid]) {
      map[v.pid] = [];
    }
    map[v.pid].push(v);
  });

  for (const pid in map) {
    let children = map[pid];
    children.forEach(child => {
      if (map[child.id]) {
        child.children = map[child.id];
      }
    });
  }
  tree.children = map[rootNode.id];
  return tree;
}

const tree = arr2tree(arr);

lhyt · 2019-08-13T16:29:49Z

function convertToTree(arr) {
  const MAP = arr.reduce((res, cur) => res.set(cur.id, cur), new Map());
  return [...MAP].reduce((result, [, value]) => {
    const { pId } = value;
    if (pId === undefined) {
      result.push(value)
    } else {
      const parent = map.get(pId);
      parent && (parent.children || (parent.children = [])).push(value);
    }
    return result;
  }, [])
}

862881015 · 2019-08-14T03:41:24Z

题目都看不懂，pid指父元素的id吗

flyfox11 · 2019-08-14T05:55:31Z

我来写一个

function recursive(pItem,cArr) {
	let findArr = cArr.filter(item=>item.pId === pItem.id)
	if(findArr.length) {
	   for(let findItem of findArr) {
		delete findItem.pId
		recursive(findItem,cArr)
	   }
	   pItem.children = findArr
	}
 }
 
 function compose(arr) {	
	arr.filter((item,index,array)=>array.findIndex(cell=>cell.id===item.id)===index) //去重
	let pArr = arr.filter(item=>!item.pId)
	let cArr = arr.filter(item=>item.pId)
	for(let pItem of pArr) {
		recursive(pItem,cArr)
	}
	return pArr
 }

changchangge · 2019-08-15T03:20:39Z

romayn-wyb · 2019-08-15T05:58:58Z

arrayToTree([...new Set(array.map(JSON.stringify))].map(JSON.parse))

function arrayToTree(data, nodesField, idField, parentIdField) {

if (!nodesField) nodesField = 'children';
idField = idField || '_id';
parentIdField = parentIdField || '_pid';

var nodes = [];


var idHash = {};
for (var i = 0, l = data.length; i < l; i++) {
    var o = data[i];
    if (!o) continue;
    var id = o[idField];
    if (id !== null && id !== undefined) {
        idHash[id] = o;
    }
    delete o[nodesField];
}


for (var i = 0, l = data.length; i < l; i++) {
    var o = data[i];
    var p = idHash[o[parentIdField]];
    if (!p) {
        nodes.push(o);
        continue;
    }
    if (!p[nodesField]) {
        p[nodesField] = [];
    }
    p[nodesField].push(o);
}
return nodes;

}

MissNanLan · 2019-08-15T09:24:51Z

Object.values(map) 将对象转为数组
学习了

pagemarks · 2019-08-16T01:25:48Z

网站类目管理需求?

lvwxx · 2019-08-16T03:01:48Z

@ZodiacSyndicate

reduce 遍历的时间复杂度不算吗？

Yxiuchao · 2019-08-17T06:36:42Z

function transformTree(arr) {
  let res = [];
  let map = arr.reduce((pre, item) => {//去重且进行构建哈希表
    pre[item.id] = item;
    return pre;
  }, {})
  console.log(map)
  for (let item of Object.values(map)) {
    if (!item.pId) {
      res.push(item);
    } else {
      const parent = map[item.pId];
      parent.child = parent.child || [];//当这个元素没有时指向一个数组并将该孩子元素增加进去含有有自己孩子时采用本来的child数组，
      parent.child.push(item)
    }
  }
  return res;
}
console.log(transformTree(arr))

Yxiuchao · 2019-08-17T06:39:04Z

var flatLs = [
{ id: 1},
{ id: 2},
{ id: 3},
{ id: 4, pid: 1 },
{ id: 5, pid: 3 },
{ id: 6, pid: 2 },
{ id: 7, pid: 4 },
{ id: 8, pid: 3 },
{ id: 9, pid: 4 }
]
const flat2tree = flatLs => {
flatLs.forEach(item => {
if (!item.pid) {
item.pid = 0;
} else {
const index = flatLs.findIndex(_item => _item.id === item.pid)
if (index !== -1) {
flatLs[index].children = flatLs[index].children || []
flatLs[index].children.push(item)
}
}
})
return flatLs.filter(item => item.pid === 0)
}
为什么代码没有缩进，[笑哭]

用Markdown语法写就有缩进了

ghost2113 · 2019-08-20T02:00:31Z

Object.values(map) 将对象转为数组
学习了

Object.values()只是获取对象可枚举属性的value值，返回一个数组

CYYSILVER · 2019-08-20T19:22:00Z

哈希表，时间复杂度O(n)

const fn = arr => {
  const res = []
  const map = arr.reduce((res, item) => ((res[item.id] = item), res), {})
  for (const item of Object.values(map)) {
    if (!item.pId) {
      res.push(item)
    } else {
      const parent = map[item.pId]
      parent.child = parent.child || []
      parent.child.push(item)
    }
  }
  return res
}

// const arr = [{id: 1}, {id:2, pId: 1}, {id: 3, pId: 2}, {id: 4}, {id:3, pId: 2}, {id: 5, pId: 4}]
// fn(arr) => [{id: 1, child: [{id: 2, pId: 1, child: [{ id: 3, pId: 2}]}]}, {id: 4, child: [{id: 5, pId: 4}]}]

const map = arr.reduce((res, item) => ((res[item.id] = item), res), {})

等同于

const map = {}
arr.forEach((item) => {
    map[item.id] = item
})

我差点还没看懂，太菜了233

creasy2010 · 2019-08-28T05:12:48Z

/**
 * @desc
 *
 * @使用场景
 *
 * @coder.yang2010@gmail.com
 * @Date    2019/8/28
 **/

let arr: {id: number; pid?: number}[] = [
  {id: 1},
  {id: 2, pid: 1},
  {id: 3, pid: 2},
  {id: 4, pid: 1},
  {id: 5, pid: 3},
  {id: 6, pid: 2},
  {id: 6, pid: 2},
  {id: 2, pid: 1},
];

interface IItem {
  id: number;
  pid?: number;
  child?:IItem[];
}

let ItemsMap: {[id: number]: IItem} = {};
let PidItemsMap: {[pid: number]: IItem[]} = {};
for (let entry of arr) {
  if(ItemsMap[entry.id] ) {
    //去重!!
    continue;
  }
  ItemsMap[entry.id] = entry;

  let _pid = entry.pid || 'master';

  if (!PidItemsMap[_pid]) {
    PidItemsMap[_pid] = [entry];
  } else {
    PidItemsMap[_pid].push(entry);
  }
}

let root = PidItemsMap['master'];

for(let entry  of Object.values(ItemsMap)) {
  entry.child = PidItemsMap[entry.id];
}

console.log(JSON.stringify(root,null,2));

qq89987112 · 2019-08-31T17:38:42Z

const arr = [{id: 1}, {id:2, pId: 1}, {id: 3, pId: 2}, {id: 4}, {id:3, pId: 2}, {id: 5, pId: 4}]
function fn (arr) {
    const cache = {}
    const res = []
    for (let index in arr) {
        const item = arr[index]
        const cacheItem = cache[item.id]
        if (!cacheItem || typeof cacheItem.id == 'undefined') {
            const refItem = cacheItem || Object.assign({}, item)
            const refParent = cache[refItem.pId] || {}
            refParent.children = refParent.children || []
            refParent.children.push(refItem)  
            cache[item.pId] = refParent
            if (cacheItem) {
                Object.assign(refItem, item)
            } else {
                cache[item.id] = refItem
            }
            !item.pId && res.push(refItem)
        }
    }
    return res
}
fn(arr)



[
    {
        "id": 1,
        "children": [
            {
                "id": 2,
                "pId": 1,
                "children": [
                    {
                        "id": 3,
                        "pId": 2
                    }
                ]
            }
        ]
    },
    {
        "id": 4,
        "children": [
            {
                "id": 5,
                "pId": 4
            }
        ]
    }
]

GoodLuckAlien · 2019-09-03T04:03:51Z

  function formatArr (arr,newArr = []){
     //去重和第一次格式化数组
     let idArr = [],obj={}
     for(let i=0;i<arr.length;i++){
         let val = arr[i]        
        if(!~idArr.indexOf(val.id)){
            idArr.push( val.id ) 
            obj[val.id] = val
           !val.pId &&  newArr.push(val) 
        }
     }
     for(let i in obj ){
         if(obj[i].pId){
            obj[obj[i].pId].children ? obj[ obj[i].pId].children.push(obj[i]) :  obj[obj[i].pId].children = [ obj[i] ]
         }
     }
     return newArr
  }

Jesseszhang · 2019-10-28T08:06:50Z

哈希表，时间复杂度O(n)

const fn = arr => {
  const res = []
  const map = arr.reduce((res, item) => ((res[item.id] = item), res), {})
  for (const item of Object.values(map)) {
    if (!item.pId) {
      res.push(item)
    } else {
      const parent = map[item.pId]
      parent.child = parent.child || []
      parent.child.push(item)
    }
  }
  return res
}

// const arr = [{id: 1}, {id:2, pId: 1}, {id: 3, pId: 2}, {id: 4}, {id:3, pId: 2}, {id: 5, pId: 4}]
// fn(arr) => [{id: 1, child: [{id: 2, pId: 1, child: [{ id: 3, pId: 2}]}]}, {id: 4, child: [{id: 5, pId: 4}]}]

@ZodiacSyndicate 👍 厉害！（提个小建议，最好复制一下对象，否则会修改原数组）

const map = arr.reduce((res, item) => ((res[item.id] = Object.assign({}, item)), res), {})

Object.assign是浅拷贝

Jesseszhang · 2019-10-28T08:16:06Z

哈希表，时间复杂度O(n)

const fn = arr => {
  const res = []
  const map = arr.reduce((res, item) => ((res[item.id] = item), res), {})
  for (const item of Object.values(map)) {
    if (!item.pId) {
      res.push(item)
    } else {
      const parent = map[item.pId]
      parent.child = parent.child || []
      parent.child.push(item)
    }
  }
  return res
}

// const arr = [{id: 1}, {id:2, pId: 1}, {id: 3, pId: 2}, {id: 4}, {id:3, pId: 2}, {id: 5, pId: 4}]
// fn(arr) => [{id: 1, child: [{id: 2, pId: 1, child: [{ id: 3, pId: 2}]}]}, {id: 4, child: [{id: 5, pId: 4}]}]

@ZodiacSyndicate 👍 厉害！（提个小建议，最好复制一下对象，否则会修改原数组）

const map = arr.reduce((res, item) => ((res[item.id] = Object.assign({}, item)), res), {})

就是应用到了引用
const fn = arr => {
const res = []
const map = arr.reduce((res, item) => {
// console.log('====res, item====', JSON.stringify(res), JSON.stringify(item));
res[item.id] = item;
// console.log('====res====', JSON.stringify(res));
return res;
}, {})
console.log('=====map====', JSON.stringify(map));
console.log('=====values====', JSON.stringify(Object.values(map)));
for (const item of Object.values(map)) {
if (!item.pId) {
res.push(item);
console.log('====res===', JSON.stringify(res))
} else {
const parent = map[item.pId];
console.log('====parent=====',JSON.stringify(parent))
parent.child = parent.child || [];
parent.child.push(item)
console.log('====parent====',JSON.stringify(parent))
console.log(JSON.stringify(res))
}
}
return res
}
const arr = [{id: 1}, {id:2, pId: 1}, {id: 3, pId: 2}, {id: 4}, {id:3, pId: 2}, {id: 5, pId: 4}]
fn(arr);
VM61519:9 =====map==== {"1":{"id":1},"2":{"id":2,"pId":1},"3":{"id":3,"pId":2},"4":{"id":4},"5":{"id":5,"pId":4}}
VM61519:10 =====values==== [{"id":1},{"id":2,"pId":1},{"id":3,"pId":2},{"id":4},{"id":5,"pId":4}]
VM61519:14 ====res=== [{"id":1}]
VM61519:17 ====parent===== {"id":1}
VM61519:20 ====parent==== {"id":1,"child":[{"id":2,"pId":1}]}
VM61519:21 [{"id":1,"child":[{"id":2,"pId":1}]}]
VM61519:17 ====parent===== {"id":2,"pId":1}
VM61519:20 ====parent==== {"id":2,"pId":1,"child":[{"id":3,"pId":2}]}
VM61519:21 [{"id":1,"child":[{"id":2,"pId":1,"child":[{"id":3,"pId":2}]}]}]
VM61519:14 ====res=== [{"id":1,"child":[{"id":2,"pId":1,"child":[{"id":3,"pId":2}]}]},{"id":4}]
VM61519:17 ====parent===== {"id":4}
VM61519:20 ====parent==== {"id":4,"child":[{"id":5,"pId":4}]}
VM61519:21 [{"id":1,"child":[{"id":2,"pId":1,"child":[{"id":3,"pId":2}]}]},{"id":4,"child":[{"id":5,"pId":4}]}]

JackFGreen · 2019-11-14T07:36:16Z

同一个问题？ #139

gauseen · 2019-11-26T09:20:56Z

const arr = [
  { id: 1, pid: null },
  { id: 2, pid: 1 },
  { id: 3, pid: 1 },
  { id: 2, pid: 1 },
  { id: 4, pid: 2 },
  { id: 5, pid: 2 },
  { id: 6, pid: 3 },
  { id: 7, pid: 3 },
  { id: 8, pid: 3 },
  { id: 9, pid: 8 },
  { id: 10, pid: 6 }
]

// 去重
const deduplication = (arr) => {
  return arr.filter((item, index) => index === arr.findIndex(child => item.id === child.id))
}

// 递归嵌套
const arrToTree = (arr, pid = null) => {
  return arr.filter(item => item.pid === pid)
   .map(item => ({ ...item, children: arrToTree(arr, item.id)}))
}

const solution = (arr) => {
  return arrToTree(deduplication(arr))
}

solution(arr)

yangjiedage · 2020-05-01T07:53:50Z

利用对象是引用类型，直接通过pId找到父元素

var data = [{id: 1}, {id: 2, pId: 1},{id: 3, pId: 2}]

function bar() {
  let dataNoRepeat = data.reduce((curr, acc) => {
    curr[acc.id] = acc
    return curr
  }, {})
  let tree = {}

  for(let key in dataNoRepeat) {
    const item = dataNoRepeat[key]
    if(item.pId) {
      let parent = dataNoRepeat[item.pId]
      if(parent) {
        if(!parent.children) {
          parent.children = []
        }
        parent.children.push(item)
      }
    } else {
      tree[item.id] = item
    }
  }

  console.log(tree)
}

bar(data)

823680621 · 2020-07-16T02:51:35Z

  function handelFn(arr) {
    let obj = {}
    let tree = {}
    async function ff(i) {
      obj[arr[i].pId].child.push(arr[i])
    }
    for (let i = 0; i < arr.length; i++) {
      arr[i].child = []
      obj[arr[i].id] = arr[i]
      if (!arr[i].pId) {
        tree [arr [i].id] = arr [i]
      } else {
        ff(i)
      }
    }
    return tree
  }

maggie-chen · 2020-07-28T03:36:35Z

同问，reduce的复杂度不用算进去么？？

maggie-chen · 2020-07-28T03:49:55Z

function fn(arr) {
    const res = []
    //创建map结构
    const map = new Map()
    for (let elem of arr.values()) { 
        map[elem.id] = elem
    }
    // 遍历读取
    for (let value of Object.values(map)) {
        if(!value.parentId){
            res.push(value)
        }else{
            const parent = map[value.parentId]
            if(!parent.children) parent.children= []
            parent.children.push(value)
        }
    }
    return res
}

823680621 · 2020-07-28T06:23:49Z

XW666 · 2021-03-31T07:56:34Z

const find12 = (arr) => {

let map = {}, obj = {}, res = []
//数组去重
arr.forEach(item => {
  if (!obj[JSON.stringify(item)]) {
    obj[JSON.stringify(item)] = item
    map[item.id] = item
  }
})
//转成树形结构
for (const item of Object.values(obj)) {
  if (!item.pid) {
    res.push(item)
  } else {
    if (map[item.pid]) {
      const parent = map[item.pid]
      parent.children = parent.children || []
      parent.children.push(item)
    }
  }
}

return res

}

xyuh111 · 2022-04-13T07:03:01Z

const map = arr.reduce((res, item) => {
    if (!item.pid) {
        res[item.id] = item
    }
    item.child = arr.filter(it => it.pid && it.pid === item.id)
    return res
}, [])

823680621 · 2022-10-11T07:26:27Z

可行吗？ arr = [{id: 1}, {id: 2, pId: 1}, {id: 3, pId: 2}, {id: 4, pId: 2}, {id: 5, pId: 4}]

…

------------------ 原始邮件 ------------------ 发件人: "Advanced-Frontend/Daily-Interview-Question" ***@***.***>; 发送时间: 2022年4月13日(星期三) 下午3:03 ***@***.***>; ***@***.******@***.***>; 主题: Re: [Advanced-Frontend/Daily-Interview-Question] 第 125 题：如何将 [{id: 1}, {id: 2, pId: 1}, ...] 的重复数组（有重复数据）转成树形结构的数组 [{id: 1, child: [{id: 2, pId: 1}]}, ...] （需要去重） (#243) const map = arr.reduce((res, item) => { if (!item.pid) { res[item.id] = item } item.child = arr.filter(it => it.pid && it.pid === item.id) return res }, []) — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***>

yygmind added the 编程题 label Dec 16, 2019

第 125 题：如何将 [{id: 1}, {id: 2, pId: 1}, ...] 的重复数组（有重复数据）转成树形结构的数组 [{id: 1, child: [{id: 2, pId: 1}]}, ...] （需要去重） #243

第 125 题：如何将 [{id: 1}, {id: 2, pId: 1}, ...] 的重复数组（有重复数据）转成树形结构的数组 [{id: 1, child: [{id: 2, pId: 1}]}, ...] （需要去重） #243

Comments

yygmind commented Aug 13, 2019

ZodiacSyndicate commented Aug 13, 2019

哈希表，时间复杂度O(n)

weiweixuan commented Aug 13, 2019

是这个意思吗，不太清楚，轻喷哈

JaniceDong commented Aug 13, 2019 • edited

McCarthey commented Aug 13, 2019

哈希表，时间复杂度O(n)

GitHubJiKe commented Aug 13, 2019

lhyt commented Aug 13, 2019

862881015 commented Aug 14, 2019

flyfox11 commented Aug 14, 2019 • edited

changchangge commented Aug 15, 2019

romayn-wyb commented Aug 15, 2019

MissNanLan commented Aug 15, 2019

pagemarks commented Aug 16, 2019

lvwxx commented Aug 16, 2019

Yxiuchao commented Aug 17, 2019

Yxiuchao commented Aug 17, 2019

ghost2113 commented Aug 20, 2019

CYYSILVER commented Aug 20, 2019

哈希表，时间复杂度O(n)

creasy2010 commented Aug 28, 2019

qq89987112 commented Aug 31, 2019 • edited

GoodLuckAlien commented Sep 3, 2019

Jesseszhang commented Oct 28, 2019

哈希表，时间复杂度O(n)

Jesseszhang commented Oct 28, 2019

哈希表，时间复杂度O(n)

JackFGreen commented Nov 14, 2019

gauseen commented Nov 26, 2019

yangjiedage commented May 1, 2020 • edited

823680621 commented Jul 16, 2020 • edited

maggie-chen commented Jul 28, 2020

maggie-chen commented Jul 28, 2020

823680621 commented Jul 28, 2020

XW666 commented Mar 31, 2021

const find12 = (arr) => {

xyuh111 commented Apr 13, 2022

823680621 commented Oct 11, 2022 via email

JaniceDong commented Aug 13, 2019 •

edited

flyfox11 commented Aug 14, 2019 •

edited

qq89987112 commented Aug 31, 2019 •

edited

yangjiedage commented May 1, 2020 •

edited

823680621 commented Jul 16, 2020 •

edited