帶分區的選擇算法

Question

我們必須將整數輸入到一個數組中。在輸入過程中，我們可以要求從最大（最大）1/3的數字中找出最小的數字，任何次數。

例如：

input 1 

input 7 

input 9 

tell the number 

input 21 

input 8 

input 5 

tell the number 

input 11 

tell the number 

輸出應爲：

9 

9 

11 

說明：

• 直到所述第一查詢的陣列將具有數字1 7 9，所以頂端1 /第三個數字是9.因爲他們只有一個數字，所以它也是最小的。
• 當第二查詢由陣列看起來像1 7 9 21 8 5，等等排序陣列將是：
  21 9 8 7 5 1，頂部1 /第三數字將是21和9最小那些 將是9
在最終查詢
• 陣列具有1 7 9 21 8 5 11，對排序21 11 9 8 7 5 1頂端1 /第三數字將是21和11最小的那些是11

數組中的整數的總數可以是25萬

我的方法是應用選擇算法與分區，但它超過了時間限制。

Answer 1

（我認爲這個問題是某種功課（「我們必須」），並相應地我不直截了當地給出答案。）

重新擬訂你的任務：你被要求找到的第66個百分在線算法。 There is already a SO question for the median，這是第50百分位，所以你應該能夠從那裏適應。如果該算法不好，請對在線算法進行一些研究，其中大部分算法也適用於您的問題。

Answer 2

爲什麼選擇算法失敗：
注意，使用選擇算法是在#elements線性。假設#requests在#elements中是線性的 - 它將導致一個二次方解決方案，這就是爲什麼你超過了時間限制。

的另一種方法： 保持兩個堆：一個最大堆H1和最小堆H2

最大堆（H1）將保持2/3最低號碼而最小堆將金1/3個最高的數字。

現在，你看每個元素x，檢查是否需要增加頂部1/3堆（H2），如果你這樣做：你需要添加max{x,H1.max()}。如果您添加了H1.max() - 您需要將其從堆中刪除，並插入x。如果不需要添加，請檢查x是否大於H2.min()，如果是，請刪除最小格式H2，將其插入到H1，並將x添加到H1。

注意：您正在尋找這種解決方案的數量可以在O(1)在任何時候發現的，它是最小堆（H2）的最小值。

總的複雜性，如果這個解決方案是O(nlogn + k) - 在n是號碼的數量，並且k是「講數」的請求的總數。

注意：一個簡單的解決方案（雖然可能較慢）將保持排序的列表（在BST或例如skiplist），並使用二進制搜索來查找相關的元素。

實施例：

init: 
H1 = {} 
H2 = {} 

input1: 
H1 = {1} 
H2 = {} 

input7: 
H1={1,7} 
H2 = {} 

input 9: //need to add a max, in this case: x > H2.max() -> add x to H2. 
H1 = {1,7} 
H2 = {9} 

tell the number 
H2.min() = 9 

input 21: // 21>9 -> remove H2.min() add it to H1, add x to H2 
H1 = {1,7,9} 
H2 = {21} 

input 8: 
H1 = {1,7,8,9} 
H2 = {21} 

input 5: //remove max from H1, add max to H2, add x to H1 
H1 = {1,7,5,8} 
H2 = {9,21} 

tell the number 
H2.min() = 9 

input 11: //remove min from H2, add it to H1, add x to H2. 
H1 = {1,7,5,8,9} 
H2 = {11,21} 
tell the number 
H2.min() = 11 

Answer 3

如何：

1. 保持陣列中的排序的方式，插入成本=的log（n）
2. 離開1/3最小值= O（1）