数组分组问题？

Question

我有一个数组，数组格式如下：

  [
    {
      id: 1,
      name: 1,
      msg: {
        masterId: 1,
        stackId: 2
      }
    },
    {
      id: 2,
      name: 2,
      msg: {
        masterId: 1,
        stackId: 2
      }
    },
    {
      id: 3,
      name: 3,
      msg: {
        masterId: 3,
        stackId: 3
      }
    },
    {
      id: 4,
      name: 4
    }
  ]

想要根据msg中的masterId和stackId进行分组，masterId标识数据属于父元素，如果masterId和id相同，说明该元素为父元素，stackId标识这个设备属于一个组，最后想得到的格式如下

[
  {
      id: 1,
      name: 1,
      msg: {
        masterId: 1,
        stackId: 2
      },
      children: [
      {
          id: 2,
          name: 2,
          msg: {
            masterId: 1,
            stackId: 2
          }
        }
      ]
    },
    {
      id: 3,
      name: 3,
      msg: {
        masterId: 3,
        stackId: 3
      }
    },
    {
      id: 4,
      name: 4
    }
]

请问该怎么做？

Answer 1

let arr = [
  {
    id: 1,
    name: 1,
    msg: {
      masterId: 1,
      stackId: 2
    }
  },
  {
    id: 2,
    name: 2,
    msg: {
      masterId: 1,
      stackId: 2
    }
  },
  {
    id: 3,
    name: 3,
    msg: {
      masterId: 3,
      stackId: 3
    }
  },
  {
    id: 4,
    name: 4
  }
];

let result = arr.reduce((acc, cur) => {
 
  let parent = acc.find(item => item.id === cur.msg?.masterId);

  if (parent) {

    if (!parent.children) {
      parent.children = [];
    }
    parent.children.push(cur);
  } else {
    acc.push(cur);
  }

  return acc;
}, []);

console.log(result);

Answer 2

时间复杂度 O(n)，示例如下：

function func(array) {
  const result = new Map();

  for (const { id, name, msg } of array) {
    if (msg && msg.masterId === id) {
      result.set(id, { id, name, msg, children: [] });
    } else if (msg && result.has(msg.masterId)) {
      result.get(msg.masterId).children.push({ id, name, msg });
    } else {
      result.set(id, { id, name, msg });
    }
  }

  return Array.from(result.values());
}