优化合并两个不同整数列表为特定元组列表的C#函数实现方案咨询

阿华AIGC实验室

2026-4-29

优化整数列表配对函数的性能方案

嘿，我来帮你优化这个配对函数的性能～先看看你当前实现的问题：你的代码用了嵌套foreach循环（时间复杂度O(n*m)），而且每次调用List.Remove都是线性查找（O(k)时间），当列表规模变大时，这会导致性能急剧下降。咱们可以用**哈希集合（HashSet）**来把时间复杂度降到O(n + m)，同时让逻辑更清晰。

优化思路

把第二个列表转换成HashSet<int>，这样元素的查找和删除操作都是平均O(1)的时间复杂度。
遍历第一个列表，逐个检查元素是否存在于HashSet中：
- 如果存在，添加(a,a)元组，同时从HashSet中移除该元素（避免重复匹配）。
- 如果不存在，收集到未匹配的列表中。
最后把第一个列表的未匹配元素以(a,null)形式加入结果，把HashSet中剩余的元素以(null,a)形式加入结果。

优化后的C#实现

internal static List<Tuple<int?, int?>> PairInts(List<int> firstList, List<int> secondList)
{
    var pairs = new List<Tuple<int?, int?>>();
    
    // 将第二个列表转为HashSet，支持O(1)的查找和删除
    var secondSet = new HashSet<int>(secondList);
    var unmatchedFirstElements = new List<int>();
    
    // 处理第一个列表的元素，匹配第二个列表的元素
    foreach (int val in firstList)
    {
        if (secondSet.Remove(val))
        {
            pairs.Add(Tuple.Create<int?, int?>(val, val));
        }
        else
        {
            unmatchedFirstElements.Add(val);
        }
    }
    
    // 添加第一个列表中未匹配的元素
    pairs.AddRange(unmatchedFirstElements.Select(val => Tuple.Create<int?, int?>(val, null)));
    
    // 添加第二个列表中未匹配的元素（剩余元素都在secondSet里）
    pairs.AddRange(secondSet.Select(val => Tuple.Create<int?, int?>(null, val)));
    
    return pairs;
}