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

Question

如何去除数组项中重复的数组项

已知 ：var arr = [5, 54, 1, 5, 1, 132, 56, 65, 132];

要求： 去除数组中重复的项目

结果： [5,54,1,132,56,65]

方法一

思路：

1. 通过循环嵌套，将索引小的数组项依次和后面的数组项进行比较
2. 出现相等情况，将后面的数组项删除（但保留位置）
3. 通过 for in 将空数组项筛除（for in 会忽略 undefined 项）

var arr = [5, 54, 1, 5, 1, 132, 56, 65, 132]; 
for(var i = 0; i < arr.length; i++){
   for(var j = i + 1; j < arr.length; j++){
   if(arr[i] == arr[j]){
   delete arr[j];
   }
   }
}
console.log(arr);

var arr2 = []

for (var key in arr) {
   console.log(arr[key]);
   arr2.push(arr[key]);
}
console.log(arr2);

方法二

var obj ={}
  for(var i = 0; i< arr.length ;i++){
  if(obj[arr[i]]){
    //若属性名已经出现过，则if内的表达式的执行结果为true，
    //对应的属性值进行加一操作；
    obj[arr[i]] = ++obj[arr[i]]; 
  }else{
    //对象未出现过，则以arr数组中的数据为属性名，
    //为obj创建一个键值对；
     obj[arr[i]] = 1;
  }
  }
  // console.log(obj);
  // 执行结果： {1: 2, 5: 2, 54: 1, 56: 1, 65: 1, 132: 2}
  var arr2 = [] ;
  //创建一个空数列
  for(var key in obj){
   arr2.push(Number(key));
   //依次推入属性名，并将属性名转成Number数据类型
   }
   console.log(arr2);
   //执行结果 [1, 5, 54, 56, 65, 132]

Answer 1

哈希表，时间复杂度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

Answer 2

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)
}
为什么代码没有缩进，[笑哭]

Answer 3

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

 //    如何将 [{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)

Answer 4

哈希表，时间复杂度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}]}]