C# .NET下将非唯一元素分配到多个列表的最高效实现方法

实现逻辑 #

核心思路是通过频次统计避免暴力逐元素对比，时间复杂度从O(n²)降低到接近线性：

• 统计母列表中每个元素的出现次数
• 最大出现次数即为所需子列表的总数量
• 每个元素出现多少次，就依次添加到前N个子列表中，确保每个子列表内无重复元素

代码实现 #

LINQ 简洁版本 #

using System.Collections.Generic;
using System.Linq;

public static class ListSplitter
{
    // 泛型实现支持任意可相等比较的元素类型
    public static List<List<T>> SplitToUniqueChildren<T>(List<T> motherList)
    {
        // 统计元素出现频次，保留元素首次在母列表中出现的顺序
        var frequencyDict = motherList
            .GroupBy(x => x)
            .ToDictionary(g => g.Key, g => g.Count());

        // 计算需要的子列表总数
        int maxFrequency = frequencyDict.Values.Max();

        // 初始化所有空子列表
        var children = Enumerable.Range(0, maxFrequency)
            .Select(_ => new List<T>())
            .ToList();

        // 为对应子列表填充元素
        foreach (var (item, count) in frequencyDict)
        {
            for (int i = 0; i < count; i++)
            {
                children[i].Add(item);
            }
        }

        return children;
    }
}

无LINQ高性能版本 #

如果要避免LINQ的微小开销，可使用原生Dictionary实现：

using System.Collections.Generic;

public static class ListSplitter
{
    public static List<List<T>> SplitToUniqueChildren<T>(List<T> motherList)
    {
        var frequencyDict = new Dictionary<T, int>();
        foreach (var item in motherList)
        {
            if (frequencyDict.ContainsKey(item))
                frequencyDict[item]++;
            else
                frequencyDict[item] = 1;
        }

        int maxFrequency = 0;
        foreach (var count in frequencyDict.Values)
        {
            if (count > maxFrequency)
                maxFrequency = count;
        }

        var children = new List<List<T>>();
        for (int i = 0; i < maxFrequency; i++)
        {
            children.Add(new List<T>());
        }

        foreach (var pair in frequencyDict)
        {
            var item = pair.Key;
            var count = pair.Value;
            for (int i = 0; i < count; i++)
            {
                children[i].Add(item);
            }
        }

        return children;
    }
}

测试用例 #

List<int> motherlist = new List<int> { 1, 1, 2, 5, 7, 2, 2, 2, 6, 1 };
var children = ListSplitter.SplitToUniqueChildren(motherlist);

// 验证总元素数和母列表一致
Console.WriteLine(children.Sum(l => l.Count)); // 输出10

性能说明 #

该方案处理10万级长度的列表耗时仅为毫秒级，完全解决暴力方案的性能问题。如需调整子列表内的元素顺序，可在统计频次后对字典键集合做自定义排序再填充。

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