如何优化时间复杂度为O(n²)的数组对象匹配算法？

原问题与代码 #

你当前实现的算法用于匹配两个对象数组，逻辑是：当allGroups中对象的id与clientsGroups中对象的clientGroupID匹配时，为allGroups的副本添加inGroup: true属性，并写入对应clientsGroups对象的id。原代码如下：

const allGroups = [{ id: '12345', name: 'groupOne'}, {id: '23421', name: 'groupTwo'},
{id: '28182', name: 'groupThree'}]

const clientsGroups = [{ id: 'abcde', clientGroupID: '12345'}, {id: 'dfcdae', clientGroupID: '93282'},
{id: 'jakdab', clientGroupID: '28182'}, {id: 'oiewad', clientGroupID: '93482'}]

const updateClientGroups = (allGroups, clientsGroups) => {
  let allGroupsCopy = [...allGroups];
  for (let i = 0; i < allGroupsCopy.length; i++) {
    const allGroupsId = allGroupsCopy[i].id;
    for (let j = 0; j < clientsGroups.length; j++) {
      if (allGroupsId === clientsGroups[j].clientGroupID) {
        allGroupsCopy[i] = {
          ...allGroupsCopy[i],
          inGroup: true,
          clientGroupID: clientsGroups[j].id,
        };
      }
    }
  }
  return allGroupsCopy;
};

原算法使用嵌套循环，时间复杂度为O(n²)（当两个数组规模相近时），可以通过哈希映射的方式将时间复杂度优化到O(n+m)（n为allGroups长度，m为clientsGroups长度）。

优化实现方案 #

核心思路是先将clientsGroups转换为以clientGroupID为键、对应id为值的哈希映射表，这样后续匹配时可以直接通过键查找，时间复杂度为O(1)。

代码实现

const allGroups = [{ id: '12345', name: 'groupOne'}, {id: '23421', name: 'groupTwo'},
{id: '28182', name: 'groupThree'}]

const clientsGroups = [{ id: 'abcde', clientGroupID: '12345'}, {id: 'dfcdae', clientGroupID: '93282'},
{id: 'jakdab', clientGroupID: '28182'}, {id: 'oiewad', clientGroupID: '93482'}]

const updateClientGroups = (allGroups, clientsGroups) => {
  // 构建clientGroupID到clientID的映射表，时间复杂度O(m)
  const clientGroupMap = new Map();
  for (const item of clientsGroups) {
    clientGroupMap.set(item.clientGroupID, item.id);
  }

  // 遍历allGroups生成结果数组，时间复杂度O(n)
  return allGroups.map(group => {
    const matchedClientID = clientGroupMap.get(group.id);
    if (matchedClientID) {
      return {
        ...group,
        inGroup: true,
        clientGroupID: matchedClientID
      };
    }
    // 未匹配的元素保留原结构（与原逻辑一致）
    return {...group};
  });
};

替代方案（用普通对象构建映射）

如果键都是字符串类型，也可以用普通对象替代Map，效果一致：

const updateClientGroups = (allGroups, clientsGroups) => {
  const clientGroupMap = {};
  for (const item of clientsGroups) {
    clientGroupMap[item.clientGroupID] = item.id;
  }

  return allGroups.map(group => {
    const matchedClientID = clientGroupMap[group.id];
    if (matchedClientID) {
      return {
        ...group,
        inGroup: true,
        clientGroupID: matchedClientID
      };
    }
    return {...group};
  });
};

优化说明 #

1. 时间复杂度优化：原嵌套循环需要遍历n*m次，优化后仅需遍历n+m次，数组规模越大，效率提升越明显。
2. 逻辑一致性：优化后的代码保持了原逻辑——仅修改匹配的元素，未匹配的元素保留原结构，且不会修改原数组的任何元素。
3. 可读性提升：使用map和哈希映射的方式，代码逻辑更清晰，易于维护。

内容的提问来源于stack exchange，提问作者elguapo