获取字典中最大的密钥

Question

我有一个包含整数键的字典.我想得到最大的钥匙.我不跟踪密钥,因此它们可能是连续的(例如1,2,3,4,5,6),但可能会跳过(1,3,4,5),尽管我怀疑这有什么不同.

我只是使用二分搜索还是有方法？据我所知,你几乎无法击败二元搜索这么简单的任务 - 也许你可以把它减半.

Answer 1

如果您有LINQ可用,您应该能够:

myDictionary.Keys.Max();

Answer 2

二进制搜索是最快的,但不能对正常字典起作用,因为密钥不以任何特定顺序存储.@ Minitech使用Linq的答案,Max()如果您使用普通字典,则最简单.

如果这是一项操作,您将需要多次执行,您可以考虑转移到SortedDictionary<TKey, TValue>基于键对条目进行排序的操作.

var dict = new SortedDictionary<int, int> {{3, 0}, {12, 0}, {32, 0}, 
                                           {2, 0}, {16, 0}, {20, 0}};
Console.WriteLine(dict.Keys.Last()); //prints 32

编辑:这可能比普通字典慢.我想如果提到那就好了.那是因为字典中的条目以不同的方式存储(红/黑树vs散列桶/散列表)

还有就是该点SortedDictionary变得比正常的快Dictionary.然而,这可能会出现大约100万件物品,但这只是猜测.事实证明它在那么多项目上快了大约10倍(但我们谈论的是100秒,所以它真的重要吗？).对于100000个项目,它在x64版本上大致相同.考虑到在字典中添加项目会产生额外的开销,这可能不值得.另外,我通过重写比较器来"欺骗"一点,所以它会按相反的顺序排序,所以我实际上是在做dict.Keys.First()而不是最后一个来获得最大的项目.

如果您需要按顺序迭代所有键值对,那么SortedDictionary真正意味着.我认为@ SimonMourier的答案可能是最好的.我保证你最快,最小的开销.