快捷方式

我的工作在C＃4.0和我有以下問題：快捷方式

給定的實數的有限集合S和參數k（不一定在SET），發現S中最小的數字大於或等於k。

很明顯，我可以使用平衡二叉樹來做到這一點。但是，在C＃中沒有這樣的數據結構可以幫助我。 C＃中的算法和可能的實現有哪些選項？

編輯：

，因爲大多數的人更感興趣的不是真正幫助批評，我會更多地解釋：

它是劃分在百萬件的實際功能的算法（或箱，就像直方圖一樣），我需要找到包含k的片段並有效地在其中應用一些計算。這些作品是形式[a; b）並且不重疊。

我正在設計的方法需要考慮片段k，並且性能至關重要，因爲它應該被稱爲每秒數千次。因此，O（n）搜索是不可接受的。

構建S的數據結構所浪費的時間並不重要，也不重要，因爲該集只會被構建一次而且永遠不會改變（它是不可變集）。

我知道我可以使用紅色的黑色樹，它具有O（log n）搜索複雜性。但是，我想研究其他算法選項（可能還有C＃中的現有實現）。

來源

2012-10-10 TapiocaCom

那麼這是一個家庭作業或面試問題？ – RQDQ

@RQDQ你問的原因是什麼？ –

「在C＃中沒有實現這樣的數據結構可以幫助我」 - 然後實現一個（或找到別人的實現）！ –

簡單的方法是（O(N)）：

double k = 3.5; 
List<double> S = new List<double>() { 1, 3, 5, 7, 9, 2, 4, 5, 6, 8, 10 }; 

var min = S.Where(f => f >= k).Min(); //4

如果你的列表已經排序，則成本O(LogN)

List<double> S = new List<double>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

var index = S.BinarySearch(k); 
var min = index > 0 ? S[index] : S[~index];

來源

2012-10-10 20:27:11

有興趣看看'S.Sort（）。First（f => f> = k）;'有沒有更快的... –

@DStanley Sort是O（N * LogN）操作，但上面代碼的代價是上）。（只是*列表中的一個*） –

平衡二叉樹是O（log n）。 – TapiocaCom

這個問題在O（n）時間內解決是微不足道的。遍歷所有元素，跟蹤迄今爲止符合條件的最小元素（不小於k）。

如果具有不同的k-重複：二進制搜索排序後的數組O（log n）的

如果最大元素大小爲界，一個桶排序等架構將得到O（1）時間。

來源

2012-10-10 20:20:48 digitalvision

爲什麼一個桶排序架構是O（1）？ – TapiocaCom

不是「最快」，但SortedList可能是「不夠快」：

public static class Extensions 
{ 
    public static double FindSmallestGreaterThan(this SortedList<double,double> list, double value) 
    { 
     foreach(double d in list.Keys) 
     { 
      if(d > value) return d; 
     } 
     throw new IndexOutOfRangeException("No values in the list greater than " + value.ToString()); 
    } 
}

用法是：

SortedList<double,double> list = new SortedList<double,double>(); 
list.Add(0.5, 0.5); 
list.Add(1.9, 1.9); 

double d = list.FindSmallestGreaterThan(1.0);

來源

2012-10-10 20:25:58

這段代碼是O（n），因爲我必須迭代整個列表。我不想討論代碼，但在c＃中的算法和替代。 – TapiocaCom

嗯，你可以使用SCG.SortedSet，這一點，在幕後，紅黑樹。

您可以使用SCG.List或數組，對其進行排序並使用其BinarySearch()方法。

您也可以使用C5 Collections Library。

如果這是家庭作業，你可以推出自己的實現（可能是教授想要的，我想象的）。有很多選項。

來源

2012-10-10 20:27:25

回答

相關問題