查找項目有了最大值小於另一個值

class SurveyData(){ double md; double tvd; }

我有一個已經升序排列這些值的列表。我想查找並返回列表中對象的索引，其中最大tvd值小於或等於double。我怎樣纔能有效地完成這項任務？

2011-10-13 John

假設你有LINQ和樂於使用TakeUntil從MoreLINQ，我懷疑你想：

var maxCappedValue = values.TakeUntil(data => data.Tvd >= limit) 
          .LastOrDefault();

，將讓你的第一個實際值，而不是指數，但你總是做：

var maxCappedPair = values.Select((value, index) => new { value, index }) 
          .TakeUntil(pair => pair.value.Tvd >= limit) 
          .LastOrDefault();

索引/值對。在兩種情況下，如果所有值均超出限制，結果將爲空。

當然，使用二分查找會更高效 - 但也稍微複雜一些。您可以使用極限TVD創建一個「虛擬」值，然後使用List<T>.BinarySearch(dummy, comparer)，其中comparer將執行通過TVD進行比較的IComparer<SurveyData>。然後，您需要檢查返回值是否爲非負數（完全匹配找到）或負數（完全匹配未找到，返回值是插入將插入的補碼）。

複雜度的差異在簡單掃描的O（n）或二進制搜索的O（log n）之間。不知道列表有多大（或者性能有多重要），很難指出二進制搜索的額外實現複雜性是否值得。

來源

2011-10-13 15:52:59

如果列表按升序排列，不應該是'values.TakeWhile（data => data.Tvd <= limit）.LastOrDefault（）'？ –

@ThomasLevesque：你說的沒錯。我可以發誓，它原來說它是按降序排列的...... –

看起來'TakeUntil'來自'System.Reactive.Linq'（和其他的homespun實現），而'TakeWhile'在香草LINQ（即，['TakeUntil'不是]（http://msdn.microsoft.com/en-us/library/vstudio/system.linq.enumerable_methods%28v=vs.100%29.aspx））？對不起 - 很小，但被*「假設你有LINQ」*而沒有找到'TakeUntil'。 – ruffin

先對小於或等於過濾器值（Where）的對象進行過濾，然後選擇這些對象值的最大值。

由於它已經以升序排列，只需遍歷該集合，直到找到大於過濾器值的值，然後返回上一個索引。

來源

2011-10-13 15:51:49 ravuya

這裏是一種使用LINQ做到這一點：

int indexOfMax = 
    data.Select((d, i) => new { Data = d, Index = i }) // associate an index with each item 
     .Where(item => item.Data.tvd <= maxValue) // filter values greater than maxValue 
     .Aggregate(// Compute the max 
      new { MaxValue = double.MinValue, Index = -1 }, 
      (acc, item) => item.Data.tvd <= acc.MaxValue ? acc : new { MaxValue = item.Data.tvd, Index = item.Index }, 
      acc => acc.Index);

但是，在這樣的情況下，LINQ的可能不是最好的選擇......一個簡單的循環會更清晰。

來源

2011-10-13 15:56:17

查找項目有了最大值小於另一個值

回答

相關問題