如何高效分组对象并更新双向关联项的val为最大值？

现有对象数组：

const resultSet = [
    {
        start: 'A',
        end: 'B',
        val: 1
    },
    {
        start: 'B',
        end: 'C',
        val: 3
    },
    {
        start: 'B',
        end: 'D',
        val: 1
    },
    {
        start: 'B',
        end: 'A',
        val: 4
    },
    {
        start: 'C',
        end: 'B',
        val: 1
    }
]

要求：将start与end互为反向的对象（如第一个与第四个）的val统一更新为这些对象val中的最大值，最终结果如下：

const finalSet = [
    {
        start: 'A',
        end: 'B',
        val: 4
    },
    {
        start: 'B',
        end: 'C',
        val: 3
    },
    {
        start: 'B',
        end: 'D',
        val: 1
    },
    {
        start: 'B',
        end: 'A',
        val: 4
    },
    {
        start: 'C',
        end: 'B',
        val: 3
    }
]

已通过以下代码生成带排序后字符串标识的数组：

const strArray = resultSet.map(element => {
    return {
        str: [element.start, element.end].sort().join(''),
        val: element.val
    }
})

console.log(strArray)

得到结果：

[
  { str: 'AB', val: 1 },
  { str: 'BC', val: 3 },
  { str: 'BD', val: 1 },
  { str: 'AB', val: 4 },
  { str: 'BC', val: 1 }
]

请问如何高效按str分组并取最大值更新val？是否有更优实现方案？

一、基于现有strArray的分组更新方案 #

先通过遍历strArray，用对象存储每个str对应的最大val，再遍历原数组完成更新：

// 统计每个str对应的最大val
const maxValMap = {};
strArray.forEach(item => {
    if (!maxValMap[item.str] || item.val > maxValMap[item.str]) {
        maxValMap[item.str] = item.val;
    }
});

// 更新原数组的val值
const finalSet = resultSet.map(element => {
    const key = [element.start, element.end].sort().join('');
    return {
        ...element,
        val: maxValMap[key]
    };
});

console.log(finalSet);

该方案时间复杂度为O(n)，仅需两次遍历，效率较高。

二、更优的一步到位方案 #

无需额外生成strArray，直接通过两次遍历原数组完成统计与更新，还可优化重复生成key的操作：

// 缓存每个元素的key与原始数据，避免重复排序拼接
const elementsWithKey = resultSet.map(element => {
    const key = [element.start, element.end].sort().join('');
    return { ...element, key };
});

// 统计每个key对应的最大val
const maxValMap = {};
elementsWithKey.forEach(item => {
    if (!maxValMap[item.key] || item.val > maxValMap[item.key]) {
        maxValMap[item.key] = item.val;
    }
});

// 生成最终结果数组
const finalSet = elementsWithKey.map(item => ({
    start: item.start,
    end: item.end,
    val: maxValMap[item.key]
}));

console.log(finalSet);

此方案减少了重复生成排序字符串的开销，在数组规模较大时性能优势更明显，整体时间复杂度仍为O(n)。

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