我有一个键为整数的字典,我想获取最大的键。我没有追踪过这些键,所以它们可能是连续的(例如1,2,3,4,5,6),但可能会跳过一些(1,3,4,5)。不过我认为这并不会产生任何影响。
我应该只使用二分查找还是还有其他方法?就我所看到的,对于这样一个简单的任务,你几乎无法打败二分查找 - 也许你可以把它减半。
我有一个键为整数的字典,我想获取最大的键。我没有追踪过这些键,所以它们可能是连续的(例如1,2,3,4,5,6),但可能会跳过一些(1,3,4,5)。不过我认为这并不会产生任何影响。
我应该只使用二分查找还是还有其他方法?就我所看到的,对于这样一个简单的任务,你几乎无法打败二分查找 - 也许你可以把它减半。
如果您有可用的LINQ,您应该能够执行以下操作:
myDictionary.Keys.Max();
Imports System.Linq
并在.net 3.5+中编译 - 然后就可以愉快地工作了 :) - HeavenCoreO(n)
还是O(1)
的顺序? - Pixel_95如果您使用的是普通字典,二分查找可能是最快的,但无法起作用,因为键不以任何特定顺序存储。如果您正在使用普通字典,则 @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
编辑:这个方法可能比一个普通的字典要慢。我想提一下这点应该是好的。那是因为字典中的条目以不同的方式存储(红黑树与哈希桶/哈希表)。
SortedDictionary
比普通Dictionary
更快确实存在一个点。然而,这可能需要大约100万项左右,但这只是猜测。当达到那么多项时,它大约快了10倍(但我们只谈论几百分之一秒,所以真的重要吗?)。在x64版本中,对于100000项,它差不多相等。考虑到添加项到字典的额外开销,这可能不值得。此外,我“作弊”了一下,通过重写比较器使其按相反的顺序排序,所以我实际上是使用dict.Keys.First()
而不是最后一个来获取最大项。
SortedDictionary
确实是为了按顺序迭代所有键值对而设计的。我认为@SimonMourier的回答可能是最好的。我保证这是最快的,开销最小。
dict.Last().Key;
- Jordan public class RememberMaxDictionary<K, V> : IDictionary<K, V> where K: IComparable<K>
{
private Dictionary<K, V> _inner;
public RememberMaxDictionary()
{
_inner = new Dictionary<K, V>();
}
public K MaxKey { get; private set; }
public void Add(K key, V value)
{
_inner.Add(key, value);
if (key.CompareTo(MaxKey) > 0) // test null if needed
{
MaxKey = key;
}
}
... TODO implement the rest...
Dictionary<K, V>
没有排序,但值得一提的是,有一些有序实现的IDictionary<K, V>
存在。 - phoog