c# - 如何找到集合中的下一个最大键？

Question

假设我有一本 C# 字典。假设键是可比较的，我如何找到大于给定 k 的最小键(与字典键的类型相同)？但是，我想使用像 SortedDictionary 这样的集合来高效地执行此操作。

显然，如果不是高效执行的问题，可以从任何字典开始，提取其键，然后使用具有合适谓词的 First 方法。但这将在线性时间(以键的数量)执行，如果一个人有一组排序的键，那么应该能够在对数时间内找到键。

谢谢。

Answer 1

SortedList<TKey, TValue>类(class)工具IDictionary<TKey, TValue>并且有一个 IndexOfKey方法;我想这就是你想要的:

// I'm just going to pretend your keys are ints
var collection = new SortedList<int, string>();

// populate collection with whatever

int k = GetK(); // or whatever

int kIndex = collection.IndexOfKey(k);

int? smallestKeyGreaterThanK = null;
if (collection.Count > kIndex + 1)
    smallestKeyGreaterThanK = collection.Keys[kIndex + 1];

根据MSDN documentation :

This method performs a binary search; therefore, this method is an O(log n) operation.

编辑:如果您不能确定字典是否包含您正在寻找的键(您只想要下一个最大的键)，仍然有一种方法可以利用现有的二进制文件.NET 的搜索方法供您使用。你说你正在寻找一个“高效”的解决方案；如果您的意思是您的时间(以及代码行)，则以下内容符合该标准。另一方面，如果你的意思是内存使用或性能，它可能并不理想。无论如何:

List<int> keysList = new List<int>(collection.Keys);
int kIndex = keysList.BinarySearch(k);

现在，BinarySearch会给你你要找的东西，但如果 key 不在那里，那就有点古怪了。返回值，来自MSDN documentation , 如下:

The zero-based index of item in the sorted List<T>, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.

这意味着您需要添加另一行:

kIndex = kIndex >= 0 ? kIndex : ~kIndex;