查找集合中下一個最小和最大數字的快速算法

Question

我有一組正數。給定一個不在集合中的數字，我想查找集合中下一個最小的和下一個最大的數字是。我現在想的唯一辦法就是通過減少1來找到下一個最小值，直到找到一個數字爲止，然後再找到下一個最大值。

動機：我有一堆數據在一個hashmap中，按日期鍵。我沒有每個日期的數據點。如果我的數據是10/01/2000 60和10/05/2000 68，我要求10/02/2000，我想要線性插值。我應該得到62.

Answer 1

這取決於您的設備是否被排序。

如果您的設置未排序，那麼找到最接近的（更高和更低）是一個O（n）操作和一個相當簡單的算法。

如果您的集合已排序，那麼您可以使用修改的二分搜索來查找O（log n）中的答案，這顯然比較大的集合更好。

如果你反覆這樣做，它可能是值得排序的集合，這會產生O（n log n）的成本，可能會一次關閉或不取決於頻繁集合更改的頻率。隨着新項目的添加，某種樹排序可能有助於改進未來的排序。

Answer 2

將您的數據項放入樹中，如AVL樹，red-black tree或B +/B-樹。然後你可以搜索有序的值。

Answer 3

如果您在數組中獲得鍵，則可以對數組進行排序，並查找最後一個小於所需元素的元素的索引。然後你直接在你想要的點之前知道鍵的索引，並且在那之後的下一個元素就是之後的那個元素。

這應該給你足夠的插值。 （使用的數據結構不一定是數組，任何可以排序的數據都是很好的。如其他人所建議的那樣，平衡二叉樹是理想的，尤其是如果您計劃稍後重用數據的話）。

Answer 4

對數字進行排序，然後對每個鍵進行二分搜索以平分該組。然後，您可以找到哪些數字位於丟失鑰匙的兩側。

Answer 5

將集合轉換爲列表並對其進行排序，然後對未在集合中的數字執行二分搜索。結果將是插入點，即數字在其出現的位置。如果您調用n，則排序列表的索引n上的元素是下一個最小的數字，排序列表的索引n+1上的元素是下一個最大的數字。

您還可以通過在構建時按照排序順序執行此操作，然後搜索插入點變得很容易。這種方法被例如Java的TreeMap的floorEntry()和ceilingEntry()方法。

Answer 6

將您的設置保存爲排序列表/數組並執行二分搜索：例如，在Python中，排序列表和標準Python庫中的bisect模塊可以滿足您的需求。

Answer 7

所有這些歸結爲是binary search，只要你能得到你的數據排序。有兩種選擇。

1. 排序容器
   如果你把你的號碼中的一個排序容器，這是很容易的。將數據放在TreeMap中，而不是使用HashMap，那麼您可以高效地找到下一個更高或更高的元素。Java的甚至有方法做你想要什麼：

   • higherKey(K)
   • lowerKey(K)

   這是有效的，因爲TreeMap使用red-black tree（一種balanced binary search tree）內部。 higherKey和lowerKey只需從根開始並遍歷樹來查找元素應該到達的位置。

   我不知道你所使用的語言，但在C++中，你會用std::map，以及類似的方法是：

   • iterator lower_bound(const key_type& k)
   • iterator upper_bound(const key_type& k)

2. 陣列+排序
   如果你不想保持你的數據一直排序，你總是可以轉儲你的d ATA到一個數組（或任何隨機接入容器），使用sort，然後用陣列上的STL的二進制搜索例程：

   • lower_bound
   • upper_bound

   在Java模擬將是將東西轉儲到ArrayList中，請致電Java的sort()，然後使用binarySearch()。

所有的搜索程序這裏有O（LOGN）時間。保留您的數據排序的成本是O（nlogn）與排序的容器或與陣列。對於已分揀的集裝箱，成本分攤爲n插入;您撥打sort()時，您可以一次付清所有費用。

如果你不想東西都進行排序，你可以隨時使用linear search，但你會付出，如果你使用了很多，因爲它是一個爲O（n）算法。

Answer 8

查找未排序集合中的第n個元素是O（n）。（Select Algorithm）儘管在這裏你可以把它歸結爲一個更簡單，不太一般的算法，如果你總是想要最小的元素。但一般來說，在未排序列表內找到最小，次小等元素爲O（n）。 （你應該已經教這在你的算法類...）

排序一組，然後索引元素是O（n log n）的

的有序集合找到元素爲O（日誌n）（二進制搜索）

Answer 9

如果你知道每週都會有一個數據點，那麼保持你的HashMap保持原樣並按照你的建議做...這將是一個恆定的時間操作因爲您將執行14次哈希表查找（在您的搜索日期的每一側探查7天），每次都會執行原始操作。

如果你不知道你的數據有多密集，你可以將它保存在RAM中，然後按照許多其他人的建議將它放到一個平衡的樹狀結構中。但是如果你有很多的日期，並且你必須通過網絡從數據庫加載數據，這可能是昂貴的。