JavaScript如何高效查找嵌套数组中各名称对应的最小数值项

你原来的双层循环时间复杂度为O(n²)，数据量大的时候性能会急剧下降。我们可以通过一次遍历完成统计，时间复杂度降到O(n)，实现思路如下：

• 用普通对象或者Map存储每个名称对应的最小数值
• 遍历原数组的每一条目，对每个名称做判断：
  • 如果还没记录过这个名称，直接存入映射表
  • 如果已经记录过，对比当前条目的数值和映射表里存的数值，保留更小的那个
• 最后把映射表的键值对转成二维数组就是最终结果

实现代码 #

const items = [["bob",1],["jeff",2],["wal-E",2],["bob",1],["bob",10]];
// 用Map存每个名称的最小值，也可以用普通对象
const minMap = new Map();

for (const [name, num] of items) {
  // 不存在当前名称 或者 当前数值比已存的更小，就更新
  if (!minMap.has(name) || num < minMap.get(name)) {
    minMap.set(name, num);
  }
}

// 把Map转成要求的二维数组格式
const result = Array.from(minMap.entries());
console.log(result); // 输出 [["bob",1],["jeff",2],["wal-E",2]]

如果你需要保留同一个名称下所有数值等于最小值的条目（而非只保留一条），可以调整映射表存储结构为数组，遍历的时候判断数值等于最小值就推入，发现更小值就清空数组重新存：

const minMap = new Map();
for (const item of items) {
  const [name, num] = item;
  if (!minMap.has(name)) {
    minMap.set(name, { min: num, list: [item] });
    continue;
  }
  const curr = minMap.get(name);
  if (num < curr.min) {
    minMap.set(name, { min: num, list: [item] });
  } else if (num === curr.min) {
    curr.list.push(item);
  }
}
const result = Array.from(minMap.values()).flatMap(v => v.list);

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