如何查找集合中的下一个最大密钥？

假设我在C＃中有一本字典。假设这些密钥具有可比性，我如何找到大于给定k的最小密钥（与字典密钥的类型相同）？不过，我想用一个像SortedDictionary这样的集合来有效地完成这个任务。很显然，如果它不是一个有效地做它的问题，可以从任何字典开始，提取它的关键字，然后用合适的谓词使用First方法。但是，如果一个人拥有一组有序的密钥，那么在线性时间内（在密钥的数量上），应该能够在日志时间内找到密钥。如何查找集合中的下一个最大密钥？

谢谢。

来源

2009-12-28 banbh

该SortedList<TKey, TValue>类实现IDictionary<TKey, TValue>和有一个方法;我认为这是你想要什么：

// 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：

此方法执行二进制搜索;因此，此方法是O（log n）操作。

编辑：如果你不能肯定的是，字典包含你正在寻找的钥匙（你只是想下一个大），还有充分利用现有的二进制搜索法的方式进行从.NET为您的目的。你说你正在寻找一个“高效”的解决方案;如果您的意思是您的时间（以及代码行数），则以下标准符合该标准。另一方面，如果你的意思是在内存使用或性能方面，它可能并不理想。总之：现在

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

，BinarySearch会给你你在找什么，但如果关键不在那里，这是一个有点古怪。的返回值，从MSDN documentation，如下：

项的从零开始的索引在排序List<T>，如果项是发现;否则，一个负数那是指数比项较大下一个元素的的按位求补，或者，如果不存在较大元件，按位求补Count的。

这意味着你将需要添加另一条线路：

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

来源

2009-12-29 02:58:55

谢谢。不幸的是，在我的情况下，我不能保证集合包含k作为关键。事实上，在给出你的答案后，我现在怀疑在键上无法避免手工编码二进制搜索（在这种情况下可能更好称为二分搜索）。 – banbh 2009-12-30 01:22:51

@banbh：可能。你*可以*作弊一点，并使用'List '类提供的'BinarySearch'方法（见我的编辑）;但是这需要分配更多的内存，而您并不需要分配内存。尽管如此，如果你真的反对编写自己的二进制搜索，它会起作用。 – 2009-12-30 02:51:13

如果密钥来自未排序的字典，请不要忘记在二分查找之前对该列表进行排序。 – Aaronaught 2009-12-30 02:51:16

对于任何字典，您必须自己对键进行排序，然后对键进行二进制搜索以找到与您的值匹配的字典。

这会给你一个（n * log（n））+ log（n）的整个操作时间。

如果键已经排序，那么您可以将它减少到log（n），但对于大多数字典而言，情况并非如此。这就是说，将f（n）与f（（n * log（n））+ log（n））的函数进行比较并查看您通常需要执行多少个键变成了一个简单的事情这个操作，以及是否更好地进行线性或二分法搜索。这就是说，f（n）将总是低于f（（n * log（n））），所以最好只是线性搜索键。

来源

2009-12-28 22:41:23 casperOne

对，这就是我想要知道的！假设我从一个SortedDictionary开始，然后（我希望）它应该是直接找到我在原始问题中描述的密钥。但是，浏览MSDN帮助文件，似乎我需要重新发明轮子（如上所述），这似乎很愚蠢。 – banbh 2009-12-28 22:55:20

看起来n对于任何n都将小于n * log（n）+ log（n）。为什么比较绘图值？如果我们要遍历整个集合，则不需要sortedDictionary;一个简单的列表将在O（n）时间内始终执行此操作。 – Tarydon 2009-12-29 03:02:20

@Tarydon该声明更多地向OP指出如何找出最佳性能影响。不过，我已经改变了答案，给出了一个更明确的答案，以便更明确。 – casperOne 2009-12-29 16:47:11

你确定，使用SortedDictionary会在线性时间执行吗？由于这是微软的一个课程，我希望他们对它进行优化。

我建议你确实写一些测试方法。

BR，马塞尔

来源

2009-12-28 22:42:22 Marcel

由于SortedDictionary通过收集实现IEnumerable，为什么不循环，当你打的第一个值大于K停下来？除非你有大量的收藏品，而你的目标接近尾声，否则这应该会给你合理的表现。你的字典有多大？

来源

2009-12-29 02:54:58

如何查找集合中的下一个最大密钥？

回答

相关问题