假設我們有一個很大的整數數組 A。我們想要回答許多查詢，例如：找到索引 0 和 100 之間的最小值找到索引 4 和 90 之間的最小值...示例：A = {6, 1, 7, 5, 3}索引 0 和 1 之間的最小值為 1索引 2 和 3 之間的最小值為 5索引 0 和 4 之間的最小值為 1遍歷每個查詢的元素并找到最小值的明顯方法在性能方面是不夠的。我不知何故需要一次性存儲所需的信息，然后在恒定時間內回答查詢。所以算法不應該是二次的。需要比 O(N * M) 更好的東西。（N：數組大小，M：查詢數）我試過但找不到如何做到這一點。它一定是關于查找和存儲一些總和并以某種方式使用它們的東西。有任何想法嗎？謝謝閱讀。
2 回答
飲歌長嘯
TA貢獻1951條經驗 獲得超3個贊
要考慮的兩個選項：
每個查詢 O(n) 預計算和 O(logn)
O(nlogn) 預計算和每個查詢 O(1)
第一種方法是通過遞歸計算偶數位置的所有對的最小值，然后在 4 的倍數位置處所有 4，然后在所有 8 的倍數處所有 8，依此類推。然后，每當您想要訪問特定范圍的最小值時，您將其分解為您已經擁有的部分并計算其中的最小值。
例如，要找到元素 1..10 的最小值，請使用 1 和 2..3 和 4..7 以及 8..9 和 10 的最小值。
第二個方法是計算所有位置的所有對的最小值，然后是所有位置的所有 4，然后是所有位置的所有 8。當你有一個特定的范圍時，你將它構造為兩個部分的最小值并計算這兩個部分的最小值。
例如，要找到元素 1..10 的最小值，請使用最小值 1..8 和最小值 3..10。
慕容森
TA貢獻1853條經驗 獲得超18個贊
為每個問題制作一個“解決方案”、一個“最小值”和一個“最大值”
然后，當您傳遞到數組的下一個元素時，如果您達到問題的 Index==min，則解決方案=該索引的數量。只要您沒有達到最大值，您就可以將解決方案與該索引中的數字和實際解決方案進行比較。（好的，我在發布時意識到這是 n * m，抱歉）
添加回答
舉報
0/150
提交
取消