java - 整数流中的最大值和最小值

Question

给定一个整数流（我只能遍历一次），找到最大值和最小值的最佳解决方案是什么？我想如果我有足够的时间来处理每个数字，最简单的解决方案是将最小值和最大值简单地保存在单独的变量中，但是如果我无法处理其中的每一个，最好的方法是什么？有没有比简单地保留最大和最小变量并跳过例如每隔一个数字更好的解决方案？

Answer 1

如果您想要真正的最大值和最小值，只需使用变量跟踪它们。

根据您的输入数据，概率最小值/最大值可能“足够准确”。因此，如果您只以 50% 的机会查看每个数字，那么您可能只有 50% 的确切最小值或最大值。但可能已经有 75% 的机会至少有第二大/最小等。但是，计算随机数以进行无偏采样已经比查看所有数字的最小值/最大值要昂贵。跳过每一秒是危险的：数据中可能存在偶数/奇数模式，这会让您感到非常沮丧。