如何查找集合中的下一個最大密鑰？

假設我在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

如何查找集合中的下一個最大密鑰？

回答

相關問題