用於遍歷非重疊區間的算法

我有一個排序的非重疊區間（從零開始，半開）的列表，例如，用於遍歷非重疊區間的算法

{[0, 5), [10, 20), [35, 40)}

比方說，我有（這種情況下說，3）的區間中的一個點和+10的步長值（即向右移動10位）。有沒有一種算法可以在O（1）時間內計算我的最終位置？（編輯：也許我應該說，東西爲O更好（N））與上述區間步+10

未採用區間覆蓋被認爲是不存在的位置，所以位置3將導致19最終位置（ +1將我的位置移動到4，則剩餘的+9從位置10開始直到位置19）。另一個例子是，如果我們將15作爲開始位置，並且步驟值爲-10，那麼我們將擁有0的最終位置。

爲了簡單起見，我們還可以假設最終位置總是以一個間隔結束。然而，我們可能會或可能不知道從哪個時間間隔開始計數。

我當然可以迭代O（n）時間間隔列表（n =間隔數）。但我覺得應該有更好的方法來解決這個問題。

P.S.這個問題有一個名字嗎？這感覺應該有一個適當的名字，但我不確定它是什麼。

來源

2017-04-07 bow

難道你不能只使用預處理步驟把所有的值放入一個數組，然後在O（1）中獲取它們嗎？如果您多次執行此操作（至少Omega（n）次），那麼平均成本爲O（1）... – gdelab

通過將間隔排列到二叉樹中（非葉），可以輕鬆獲得對數時間節點應該公開其子樹的最小覆蓋區間和實際的寬度總和）。我不知道如何去持續時間。 – Useless

@Useless您是否介意在更詳細的答案中轉換您的評論？我對這些具體細節感興趣，顯然這是一個正確的渠道。 – Codor

您可以輕鬆地安排您的時間間隔爲二叉樹（非葉節點應該公開都以其子樹最小的覆蓋區間，和寬度的實際總和）

得到對數時間

因此，改變你原來設定的時間間隔的一點，

{[0, 5), [15, 20), [25,30), [35, 40)}

將表示爲像

   {cover:[0,40), size:20} 
      /      \ 
{cover:[0,20), size:10} {cover:[25,40), size:10} 
    /   \   /   \ 
{[0,5), 5} {[15,20), 5} {[25,30), 5} {[35,40), 5}

樹

其中覆蓋是涵蓋子樹的最小區間，大小是區間寬度，不包括間隙。

因此，要處理你的3 + 10情況下，我們做這樣的事情：

定期二叉樹搜索，找到包含3個區間（對數時間）
我們正在向右移動（積極的一步），並且該區間在該方向上覆蓋5-3=2。 2<10，所以我們還沒有完成：調整剩餘距離（10-2=8）並在樹中向右移動。

當前節點就是我們的父母的左子，這樣就意味着在尋找下一個
這間隔覆蓋5<8右孩子，所以我們還沒有完成。調整剩餘距離（8-5=3）並再次在樹中向右移動。

當前節點就是我們的父母權的孩子，這樣就意味着上升的水平，在這種情況下，我們的祖父母的右子
這間隔覆蓋10>3，所以我們的終點是在某處這裏。但是，這不是一片葉子，所以我們需要再次下去，從左邊的孩子開始。請注意，父/子範圍重疊，所以我們不會在此步驟中消耗任何剩餘距離。
此區間涵蓋5>3，所以我們終於找到了正確的葉子間隔。我們的終點是25 + 3 = 28

注意的是，雖然遍歷右看起來直線，我們可以跳過中間的子樹，如果有任何。現在不太清楚，但仍應該是對數。

來源

2017-04-07 12:59:03 Useless

感謝您的詳細信息。 – Codor

阿哈，存儲間隔跨度確實是一個不錯的主意。我想我現在可以更好地理解現在可以做什麼。謝謝！ – bow

用於遍歷非重疊區間的算法

回答

相關問題