1

假设我们有一个包含整数的列表，我们需要找到最小值和最大值。最好的方法是什么？我可以想到以下内容：

  1. 如果读取次数远高于写入次数；保持列表排序。每当添加一个数字时；以排序方式添加它。现在要获取最小值和最大值，我们可以获取此列表的第一个和最后一个元素。

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

还有其他更好的方法吗？

4

6 回答 6

4

假设您可以观察到列表的任何突变，您可以存储（缓存）最小值和最大值，并可能在添加/删除数字时更新缓存的值。此时，列表的顺序无关紧要。

于 2013-02-06T10:23:40.953 回答
2

您可以为此使用 Collection.max() 和 Collection.min() 静态方法...

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

使用 SortedSet 使集合自动排序。

于 2013-02-06T10:23:35.843 回答
2

我会提出一个有趣的想法：

假设您确实经常删除，尽管读取次数多于写入次数，您可能会保存一个项目数组（表示整数的对象，其中有两个对已添加项目的最小值和最大值的引用）并缓存了对先前最小值和最大值的引用（与@akaIDIOT 解决方案的区别在于这只是参考）。

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

添加项目也需要 O(1)，找出最小值和最大值也需要 O(1)。

更新中描述了删除项目：

缺点是更多的内存消耗。

如果此解决方案有误，我将删除它，如果您发现任何问题，请发表评论，无需投反对票！

更新

@akaIDIOT 在他的评论中提到了一个我错过的案例。如果您有多个最大值或最小值怎么办。

在这种情况下和其他情况下，删除最大值将需要更新指向它的所有对象，这将是最大 O(n)，但我认为平均而言它仍将保持 O(1)。如果所有值都是不同的，这将始终是 O(1)

于 2013-02-06T10:35:52.767 回答
1

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

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

于 2013-02-06T10:26:54.220 回答
0

假设您支持从列表中删除整数，无论​​哪个更高（读取或写入），拥有排序列表会使事情变得更容易并提供更好的性能。

于 2013-02-06T10:25:09.140 回答
0

您可以拥有一个维护 Min 和 Max 值的自定义列表。这将为您提供 O(1) 插入，O(1) 读取 Min 和 Max，以及 O(N) 删除，但仅在您删除 min 或 max 的情况下。

伪代码：

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).
    }

}
于 2013-02-06T10:27:16.577 回答