如何高效过滤集合中每个ID的最新版本记录（允许使用Lodash）

首先要指出：你给出的预期输出存在错误——按照“保留每个ID对应最新版本”的需求，ID=1的最新版本应该是3，正确的预期输出应为：

const filteredData = [
    { id: 1, version: 3 },
    { id: 2, version: 1 },
    { id: 3, version: 2 }
];

复杂度最优的实现思路（O(n) 时间复杂度） #

你原本的思路需要先排序（时间复杂度 O(n log n)），再遍历筛选，不是最优解。更高效的方式是用哈希表（对象/Map）记录每个ID的最新版本记录，只需遍历一次原数组即可完成筛选，时间复杂度为 O(n)。

原生JavaScript实现

const data = [
    { id: 1, version: 1 },
    { id: 1, version: 2 },
    { id: 1, version: 3 },
    { id: 2, version: 1 },
    { id: 3, version: 1 },
    { id: 3, version: 2 }
];

// 用对象存储每个ID对应的最新版本记录
const idToLatest = {};
data.forEach(item => {
    const current = idToLatest[item.id];
    // 若当前ID无记录，或当前版本更大，则更新
    if (!current || item.version > current.version) {
        idToLatest[item.id] = item;
    }
});

// 把对象的值转为数组，得到最终结果
const filteredData = Object.values(idToLatest);

Lodash实现

Lodash提供了更简洁的工具函数，同样可以实现O(n)复杂度的筛选：

方式一：groupBy + maxBy 组合

const _ = require('lodash');

const filteredData = _.chain(data)
    .groupBy('id') // 按ID分组，得到以ID为键、对应记录数组为值的对象
    .map(group => _.maxBy(group, 'version')) // 每个分组取版本号最大的记录
    .value();

方式二：reduce 直接构建结果（和原生思路一致，更高效）

const _ = require('lodash');

const idToLatest = _.reduce(data, (acc, item) => {
    const current = acc[item.id];
    if (!current || item.version > current.version) {
        acc[item.id] = item;
    }
    return acc;
}, {});

const filteredData = Object.values(idToLatest);

复杂度对比 #

• 你的原思路：排序（O(n log n)）+ 遍历筛选（O(n)），总复杂度 O(n log n)
• 上述方案：仅需一次遍历（O(n)），是时间复杂度最优的实现方式

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