最大，最小平均輸入流

-1

我給出了一個輸入流&兩個指標（i & j），您需要計算所有數字的最小值，最大值平均值。我應該使用哪種數據結構&我應該如何計算這些值？最大，最小平均輸入流

似乎相當簡單。你有沒有試圖自己解決它？我們能看到你的嘗試嗎？ – Dukeling

如果有大量的索引對，這將會很有趣。前綴總和和RMQ，很好。對於一對索引來說，這絕對是微不足道的。 – harold

幾乎任何數據結構都可以，這取決於語言當然。根據不同的語言，列表可能會最快實施。計算最小值，最大值和平均值非常簡單 - 遍歷您的值。獲取每個值並將其與當前的最小值和最大值進行比較 - 如果它高於最大值或低於最小值，請替換該值，然後將該值添加到運行總計中以達到平均目的。

2013-12-09 05:37:02

一個非常簡單的解決方案就是使用簡單的數組。

數組1：輸入您只需將輸入存儲在下一個索引處。

陣列2：總：總和[I] =輸入1 +輸入[2] + ... +輸入[I]

這允許快速地平均。 O（1），但最壞情況下的最小值和最大值仍然是O（N）。

如果您需要別的方法，您可以使用segment tree並在O（log n）時間內完成所有查詢。插入也成爲O（日誌n）

2013-12-09 05:45:31 sukunrt

回答