查找任意數字下面的最大值的數據結構

我試圖找到一個數據結構，以便在我的Java項目中使用。我想要做的是從一組數字中獲得下一個最大值到任意數字以下，或者在沒有這樣的數字存在的情況下被通知。查找任意數字下面的最大值的數據結構

示例1）我的任意數字是7.0。 {3.1，6.0，7.13131313，8.0} 我需要從這個集合中得到的數字是6.0。

例2）我的任意數字是1.0。 {2.0,3.5555,999.0} 該集合中不存在下一個最高數字，所以我需要知道它不存在。

我能想到的最好的方法是通過數組進行索引和比較，一旦我完成了我的任意數字，就會返回1步。在最壞的情況下，雖然我的時間複雜度是O（n）。有沒有更好的辦法？

2013-10-03 DocSev

爲什麼不使用二進制搜索？ – yurib

維護一個搜索樹，如果它沒有，則實現一個前置函數。 –

如果您可以預處理值的列表，那麼您可以對列表（O(NLogN)時間）進行排序並執行二分法搜索，對於您想要獲得答案的每個值，將執行二分法搜索。否則你不能比O(N)做得更好。

2013-10-03 11:25:17

您需要先對數字進行排序。然後你可以做一個簡單的二進制搜索，其比較功能修改爲您的需要。在每個點檢查元素是否比輸入大，如果是這樣搜索左側或右側。最後修改後的二進制搜索應該能夠提供更直接，更小的數字，以便您輕鬆解決問題。複雜性是lg n。

2013-10-03 11:30:30 Karthikeyan

我建議你看看TreeSet.floor(...)或TreeSet.lower(...)。其中一個應該滿足您的要求，並且都具有O(logN)複雜性......假設您已經構建了TreeSet實例。

如果您只有一個排序數組，並且不想要構建TreeSet的開銷，那麼自定義二進制搜索可能是最好的選擇。

2013-10-03 11:31:06

你兩個例子組查詢排序...

如果是的話，那麼你就需要一個二進制搜索... 如果不是的話，那麼你就需要每一個元素恰好一次訪問的情況。所以需要時間n ..

2016-10-25 13:12:22

回答