僞範圍最小查詢

我的任務有問題，需要我解決類似於範圍最小查詢的問題。這個問題大致描述如下：僞範圍最小查詢

我應該編寫一個Java程序，它讀入大量的整數（大約100,000）並將它們存儲到某個數據結構中。然後，我的程序必須回答給定範圍[i，j]中的最小數量的查詢。我已經成功設計了一個算法來解決這個問題。但是，它不夠快。

我的算法的僞代碼如下：

// Read all the integers into an ArrayList 

// For each query, 
// Read in range values [i,j] (note that i and j is "actual index" + 1 in this case) 
// Push element at index i-1 into a Stack 
// Loop from index i to j-1 in the ArrayList (tracking the current index with variable k) 
[Begin loop]  
// If element at k is lesser than the one at the top of the stack, push the element at k into the Stack. 
[End of loop]

可能有人請告訴我什麼我可以這樣做，我的算法將是足夠快，以解決這個問題？

分配文件，可以在此鏈接中找到：http://bit.ly/1bTfFKa

我已經被這個問題難住了天。任何幫助將非常感激。謝謝。

來源

2013-10-15 LanceHAOH

你的問題聽起來像**完全**，就像範圍最小查詢，它有足夠的材料可用。例如，請參閱[this]（http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_%28RMQ%29）。 – Dukeling

嗨。感謝這篇文章。我發現它非常有幫助。是否可以使用基於堆棧的解決方案來解決此問題？我很想知道這一點，因爲任務簡介實際上指出rmq不是必需的，並且堆棧足以解決問題。 – LanceHAOH

如果您被告知要使用堆棧，我的猜測是您錯過了某個問題描述的詳細信息，或者錯誤地描述了它，因爲如前所述，它是RMQ，我不相信有一個有效的基於堆棧的解決方案（我們知道的）。 – Dukeling

你的問題是一個靜態範圍最小查詢（RMQ）。假設你有N個數字。您可以使用的最簡單的算法是創建一個大小爲N的數組並存儲數字的算法，另一個算法將大小爲sqrtN，並將數組中每個大小爲sqrtN的區間的RMQ保存。這應該工作，因爲N不是很大，但如果你有很多查詢，你可能想使用不同的算法。
這就是說，您可以使用的最快算法是從數字中製作一個稀疏表格，這將允許您回答O（1）中的查詢。構造稀疏表格爲O（NlogN），給定N = 10^5應該很好。
最後，最終的RMQ算法正在使用一個Segment Tree，它也支持更新（單元素和範圍），並且它是O（N）來構造Segment Tree，並且O（logN）每個查詢和更新。所有這些算法都很好地暴露了here。有關Segment Trees中的更多信息，請參閱我自己編寫的這些教程。 link
祝你好運！

來源

2013-10-16 13:45:38

感謝您的有用鏈接。他們肯定看起來很有趣。當我有更多的空閒時間時，將嘗試實施分段樹/稀疏表解決方案。無論如何，我設法通過預處理大小爲N的輸入數據，將它們分解爲大小（立方體根N）的分段。這是Dukeling提供的鏈接中所述的RMQ方法之一。 – LanceHAOH

做得好，最好的解決方案並不總是最快的或最複雜的解決方案，而是以最簡單的方式解決特定問題的解決方案。在附註中，我建議學習Segment Trees，因爲它是一個非常通用的數據結構，適用於許多範圍查詢（如範圍總和查詢，甚至GCD查詢） – 2013-10-17 14:15:44

僞範圍最小查詢

回答

相關問題