我有一個問題，其一些修改後減少到「在測距數大於x的至少指數[L，R]」查找數大於x的範圍

例如：假設一陣列A = {1, 2, 3, 6, 9, 8, 4, 3, 7, 6, 2}

而查詢是「找到至少一個元素的索引在數組A中的範圍爲[2,6]，這是大於或等於5」

回答爲上述查詢是4（用於值此指數爲6）（指數以1爲基礎）

有多個查詢，數組沒有排序（考慮到輸入已經在內存中）

有沒有一種算法，在O（logN）中查詢是可能的，其中N是否定的。排列A中的元素。

2016-03-07 Akashdeep Saluja

如果範圍[a，b]在排序順序中包含自然數a <= n <= b，那麼您可以使用二分搜索在O（log N）中解析N = #elements。 – blazs

你可以在O（（logN）^ 2）中完成。構建可以在範圍內獲得最大值的元素的分段樹。然後在[A，B]範圍內進行二分搜索，在該範圍內您嘗試查找最小索引> = A，其中範圍[A，索引]中的最大元素> = q。使用分段樹來獲取範圍[A，索引]中的最大值。這有意義嗎？ – Ghooo

@Ghooo它看起來像這個問題的正確解決方案。我懷疑我們可以在線執行'O（logN）'中的每個查詢。 –

在構建一個佔用O（N）空間的數據結構後，實際上有很多方法可以在O（log N）時間內支持查詢。

易於理解的答案

做一個二叉樹A的元素爲葉，通過索引排序。
在每個內部節點中，記錄葉子在其子樹中的最大值
您需要能夠找到給定其索引的節點的路徑。如有必要，記錄每個內部節點中第一個葉子的索引。沒有這個，你可以通過建立一個方便的形狀來建造你的樹。
現在，用一個價值發現的最小指數> = L> = X：
- 查找樹A [L]路徑
- 如果A [L] < X，然後去了直到找到包含值> = X的右側叔叔爲止的樹，沿着叔叔樹找到值> = X的第一個葉子。下降時，如果左邊的孩子有一個> = X（檢查存儲的最大值），然後向左。否則，向右走。

超高效答案

爲了使上述算法真正有效，可以在樹編碼到一個數組，像我們的堆做。在這種表示中（使用基於1的索引），您有一個數組，其中包含N-1個內部節點的最大值，然後是N個葉子。調用該數組H。然後H[i]的孩子在H[i*2]和H[i*2+1]。的H[i]父是H[i>>1]

僞代碼，使用基於1的索引，我們給出：

A[] = input array, N = input array size

我們建立^ h這樣的：

H = new array with size N*2-1, indexed from 1 to N*2-1 
for (int i=1; i<=N; ++i) 
    H[i+N-1]=A[i]; 
for (int i=N-1; i>0; --i) 
    H[i] = max(H[2*i],H[2*i+1]);

需要注意的是我們創造的孩子在父母面前，讓孩子們在那裏，當我們需要得到最大的價值。現在

，查詢功能：

//get the index of the first element with val >= minval, index >= minindex, and index <= maxindex 
//returns -1 if there is no such element 

firstAtLeast(minval, minindex, maxindex) 

    if (maxindex < minindex) 
     return -1; 

    node = minindex+N-1; //find minindex in the tree 

    //go up and right until we find a subtree that has a value >= minval 

    while(H[node] < minval) 

     //if we are a right child of our parent, go up until 
     //we have a right sibling 
     while((node&1) == 1) //node is odd 
      node = node>>1; //same as floor(node/2); 
      if (node <= 1) 
       //we went up to the root 
       //there is no such element 
       return -1; 

     //now node is a left child. try its right sibling   
     ++node; 

    //We found a subtree. get the first valid leaf 

    while(node < N) //while it's an internal node 
     node = 2*N; //left child 
     if (H[node] < minval) 
      ++node; //left child not valid - move to right child 

    //Found leaf. get index in A[i] and check against maxindex 

    index = node-(N-1); 
    return (index <= maxindex ? index : -1);

這滿足了爲O查詢（日誌N）的時間的要求。如果知道不會有小於maxindex的回答，那麼退出的時間會很長（也不會太困難），但這會使僞代碼不那麼清晰，所以我將其留作練習

來源

2016-03-07 16:17:59

製作二叉樹後，需要O（N log N）的時間，而不是在OP的原始註釋中提到的O（N）。 –

它只需要O（N）來製作二叉樹。您不必通過重複插入來構建它 –

@ShaneMacLaughlin解釋如何在O（N）中構建樹時，如果您已經知道排序，則不適用於評論。如果你想打開一個問題，我會回答 –

O（logN）接縫是不可能的。您至少需要讀取輸入，直到第一個元素更大（這可能是最後一個元素或根本沒有）。所以在最壞的情況下，你需要讀取整個輸入，這意味着O（N）。如果你輸入像的一些額外的結構來分類比你能改進算法O（logN）的

改善時纔有可能。

如果有多重查詢，您仍然需要O（logN）。您可以一次檢查多個查詢，並且還可以緩存相同查詢再次出現的結果。

來源

2016-03-07 11:08:45 MrSmith42

編輯該問題。輸入在內存中。並且針對不同的範圍和不同的搜索值有多個查詢。 –

如果可能元素的數量很小（比如說K）並且可以很容易地枚舉，那麼對於N個元素的數組，您可以使用counting sort按順序N + K排序它們。然後，您可以使用二進制搜索來查詢您的查詢，這將成爲訂單日誌N.注意，計數排序還需要訂購K存儲器，因此僅適用於相對少量的離散按鍵在使用時。如果您有Q查詢，則複雜度爲O（（N + K）+ Q（log（N））

來源

2016-03-07 11:35:34

你能解釋如何在排序後執行每個查詢嗎？ –

給定範圍L的低端和範圍H的高端，搜索L，如果最近添加一個索引位置 H，搜索H減1，稱爲結果IH。如果IL <= IH返回IL否則返回未找到。注意這是2 log N也是O（log N）。 –

我沒有得到你以前的評論，使用計數排序排序後，你如何使用二進制搜索。 –

如果您有很多查詢，並且數據量適中，則可能會獲得體面通過O（N）額外存儲加速您的查詢

創建一個元組aarray (a[i], i)（即數組中的值，該值的索引），按第一個排序（並且在衝突的情況下，然後使用二進制搜索來找到您的起點，如果該指數超出您的範圍，請繼續遍歷您的排序列表，直到您找到一個落在您感興趣的範圍內的指數。

我懷疑這個算法是O（N），最壞的情況是，所以我想它有可能做得更好。

來源

2016-03-07 12:53:40 Vatine

查找數大於x的範圍

回答

易於理解的答案

超高效答案

相關問題