从列表中获取最小和最大数字

Question

假设我们有一个包含整数的列表，并且我们需要查找最小值&（最大值）。什么是最好的方式来做到这一点？我能想到以下几点：

1. 如果大量的读取比写要高得多;按排序方式保存列表。每当添加一个数字时;以排序的方式添加它。 现在得到最小和最大，我们可以得到这个 列表的第一个和最后一个元素。

2. 如果写入次数高于读取次数，迭代列表并返回结果。但这是O（n），看起来很昂贵。

还有其他更好的方法吗？

Answer 1

假设您可以观察列表中的任何突变，您可以存储（缓存）最小值和最大值，并可能在添加/删除数字时更新缓存的值。在这一点上，列表的顺序并不重要。

Answer 2

您可以使用Collection.max（）和Collection.min（）静态方法为...

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/Collections.html

使用的SortedSet有收集自动排序。

Answer 3

假设您支持从列表中删除整数，无论​​哪个更高（读取或写入），使用排序列表可以使事情更轻松并提供更好的性能。

Answer 4

您还可以使用像数据结构（红黑树）min/max heap保留整数。获取最小/最大值将花费O(1)时间，插入一个新元素将需要O(log n)时间。

http://en.wikipedia.org/wiki/Min-max_heap

Answer 5

您可以维持的最小值和最大值的自定义列表。这会给你O（1）插入，O（1）读取Min和Max，以及O（N）删除，但只有在你删除最小或最大的情况下。

伪代码：

public MinMaxList 
{ 
    property Min; 
    property Max; 

    method Add (int newValue) 
    { 
     if (Min is null OR newValue < Min) 
      Min = newValue; 

     if (Max is null OR newValue > Max) 
      Max = newValue; 
    } 

    method Delete (int value) 
    { 
     if (value = Min or value = Max) 
      //Rescan list to determine new Min and Max values. This is O(N). 
    } 

} 

Answer 6

我会建议一个有趣的想法：

假设你有频繁的删除，虽然比写多读，你可能持有项目的数组（对象，表示整数，两个引用已添加项目的最小值和最大值），缓存参考以前的最小值和最大值（与@akaIDIOT解决方案的不同之处在于，这只是参考）。

堆栈中的每个值都指向先前的最大值和前一个最小值。

添加项目也将采取O（1），找出最小和最大也将采取O（1）。

删除项目在更新中描述：

缺点是更多的内存消耗。

如果这个解决方案是错误的，我会删除它，请评论，如果你发现任何问题，不需要投票！

UPDATE

@akaIDIOT在他的评论，我已经错过的情况下已经提到。如果您有多个最大值或最小值，该怎么办？

在这种情况下和其他情况下，删除最大值将需要更新指向它的所有对象，这将是最大O（n），但我认为它平均仍然保持O（1）。 如果所有的值都是截然不同的这将永远是O（1）