整數流中的最大值和最小值

Question

給定一串整數（我只能通過它們一次），找到最大值和最小值的最佳解決方案是什麼？我想，如果我有足夠的時間來處理每個數字，最簡單的解決方案就是將最小值和最大值保存在單獨的變量中，但如果我無法處理其中的每一個，最佳方法是什麼？有沒有比簡單地保持最大和最小變量更好的解決方案，並跳過例如每隔一個數字？

Answer 1

如果您想要真正的最大值和最小值，只需使用變量跟蹤它們即可。

根據您的輸入數據，概率最小值/最大值可能「足夠準確」。所以如果你只看50％機率的每個數字，那麼你可能只有50％的準確最小或最大。但是，也許已經有至少第二大/最小等的75％的機會等等。但是，計算隨機數以做一個無偏差的取樣已經比查看所有數字的最小/最大值更昂貴。每秒跳過是很危險的：數據中可能存在偶數/奇數模式，這些模式會嚴重影響您的工作。