如何高效匹配对象数组中的目标名称？寻求O(n²)复杂度优化方案

原始数据与需求 #

原始对象数组（已修正语法错误）：

let x = [
  {name: "Apple", message: {data: {}}},
  {name: "dell", message: {data: {}}}, 
  {name: "samsung", message: {data: {}}}
];

分类映射结构（已修正语法错误）：

let y = {
  laptop: ["Apple", "HP"],
  phone: ["samsung", "Motorolla"]
};

期望得到的结果结构：

const result = {
  laptop: {
    name: "Apple",
    message: { data: {} }
  },
  phone: {
    name: "samsung",
    message: { data: {} }
  }
};

当前实现复杂度为O(n²)，但该操作每秒需执行40次以上，需要更高效的实现方式。

优化方案：O(n+m)复杂度实现 #

核心思路是先构建名称到对象的哈希映射表，将单次查找操作的时间复杂度从O(n)降到O(1)，再遍历分类结构完成匹配，整体时间复杂度为O(n+m)（n为数组x的长度，m为分类结构y中所有名称的总数）。

具体实现代码

// 1. 构建名称到对象的映射表，O(n)时间
const nameToItemMap = new Map();
for (const item of x) {
  nameToItemMap.set(item.name, item);
}

// 2. 遍历分类结构生成结果，O(m)时间
const result = {};
for (const [category, names] of Object.entries(y)) {
  // 找到分类中存在于映射表的第一个对象（匹配逻辑可按需调整）
  const matchedName = names.find(name => nameToItemMap.has(name));
  if (matchedName) {
    result[category] = nameToItemMap.get(matchedName);
  }
}

console.log(result);

代码说明

• 映射表nameToItemMap仅需构建一次，若x数组固定，后续执行匹配时可直接复用，进一步降低重复执行的开销。
• 遍历分类结构时，使用find快速定位第一个匹配的名称，若需要匹配分类下所有存在的对象，可将find替换为filter并调整结果结构。
• 哈希映射的O(1)查找特性，相比原O(n²)方案，在数据量较大时性能提升显著，完全满足每秒40+次的执行需求。

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