如何高效基于公共Id合并不同类型对象列表为新类型？

好问题！既然两个列表长度相同且允许调整顺序，那咱们核心优化方向就是把O(n²)的查找开销降到O(n)——毕竟常规用FirstOrDefault按Id匹配的方式，数据量上去后性能会直线下降。下面给你两种高效的实现思路，按需选择：

方案一：字典映射（最优时间复杂度） #

这是性能最好的做法，先把其中一个列表转成以Id为键的字典，这样后续查找对应对象的时间是O(1)，整体时间复杂度为O(n)。

代码示例 #

首先定义合并后的目标类：

public class MergedAB
{
    public int Id { get; set; }
    public string StuffA { get; set; }
    public string StuffB { get; set; }
    // 按需添加其他需要保留的属性
}

然后是合并逻辑：

// 先把B列表转换成Id->B对象的字典，O(n)时间
var bLookup = listB.ToDictionary(b => b.Id);

// 遍历A列表，直接从字典取对应B对象合并，O(n)时间
var mergedResult = listA.Select(a => new MergedAB
{
    Id = a.Id,
    StuffA = a.stuffA,
    StuffB = bLookup[a.Id].stuffB
    // 填充其他需要的属性
}).ToList();

注意事项 #

• 题目说两列表长度相同，默认每个A的Id都能在B中找到，所以直接用bLookup[a.Id]没问题；如果怕出现找不到的情况，可以用TryGetValue做安全处理：

  var mergedResult = new List<MergedAB>();
  foreach (var a in listA)
  {
      if (bLookup.TryGetValue(a.Id, out var b))
      {
          mergedResult.Add(new MergedAB
          {
              Id = a.Id,
              StuffA = a.stuffA,
              StuffB = b.stuffB
          });
      }
      // 可以加找不到时的 fallback 逻辑
  }
  

• 如果列表存在重复Id，ToDictionary会抛出异常，这时候需要先做去重处理（比如取第一个出现的Id对应的对象）。

方案二：排序+双指针（低内存开销） #

如果你的内存比较紧张，不想额外维护字典的空间，可以先把两个列表按Id排序，然后用双指针遍历合并，时间复杂度是O(n log n)（主要来自排序），空间复杂度更低（除了结果列表外几乎无额外开销）。

代码示例 #

// 先对两个列表按Id排序，O(n log n)时间
var sortedA = listA.OrderBy(a => a.Id).ToList();
var sortedB = listB.OrderBy(b => b.Id).ToList();

var mergedResult = new List<MergedAB>(sortedA.Count);
for (int i = 0; i < sortedA.Count; i++)
{
    mergedResult.Add(new MergedAB
    {
        Id = sortedA[i].Id,
        StuffA = sortedA[i].stuffA,
        StuffB = sortedB[i].stuffB
    });
}

对比建议 #

• 如果追求极致性能，优先选字典映射，尤其是数据量较大的时候，O(n)的时间复杂度比排序方案快很多；
• 如果内存资源有限，或者列表本身已经是有序的，那排序+双指针会更合适。

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