c#中交换字典类型参数的复杂性

本文关键字：复杂性 类型参数 字典 交换 | 更新日期: 2023-09-27 18:14:45

我有一个Dictionary<A,B>，其中A的对象是唯一的，B的对象不是。

我想按B的对象对数据进行分组。

。

Dictionary<A,B> input = GenerateInput();
List<IGrouping<B,A>> output = input
                              .GroupBy(pair => pair.Value, pair => pair.Key)
                              .ToList();
  1. 方法的复杂度是多少?O (n) ?如果复杂度= GroupBy操作的复杂度-我没有找到值。请告诉我并提供文章链接。
  2. 有更有效/优雅的方式来做这个交换吗?

p。我显式地编写了变量input和output的类型，以表明我不需要output是Dictioany<,>类型。我需要一个通过A到B的容器

c#中交换字典类型参数的复杂性

方法的复杂度是多少?

正确，是O(n)。GroupBy使用哈希码对值进行分组;假设B具有良好的哈希函数，则构造组表的平摊代价为O(n)，其中包括"增长"每个组的平摊代价。

是否有更有效/优雅的方法来做这个交换?

O(n)是最有效的。您可以根据分组构建一个字典，而不是一个列表:

IDictionary<B,List<A>> output = input
    .GroupBy(pair => pair.Value)
    .ToDictionary(g => g.Key, g => g.Select(p.Key).ToList());
相关文章：