获取整数集合中最大数字的最高效方法

Question

问题：从整数集合中获取最大数的最有效方法

我最近在讨论这个问题，我有两种解决方案： 1）遍历整个集合并找到最大数（下面是代码） 2）使用排序算法。

第一个方法的效率为O(n)。

int getHighestNumber(ArrayList<Integer> list)
    {       
        if(list != null && list.size() > 0)
        {
            if(list.size() == 1)
                return list.get(0);

            int maxNum = list.get(0);
            for(int item:list)
            {
                if(item > maxNum)
                    maxNum = item;
            }
            return maxNum;          
        }
        return null;
    }

我想问一下：“在任何给定的输入上，是否有任何排序算法能够在时间尺度上超越它（如如果集合已经排序或未排序）？”还有比这更好的方法吗？

- chitresh sirohi

---

除非你了解数据的一些信息，否则每个元素都有可能是最大值。 - Oliver Charlesworth

Answer 1

如果集合已经排序，您可以在 O(1) 的时间复杂度内找到最大的元素（假设集合支持随机访问或者 O(1) 访问集合中持有最大元素的末尾 - 如果最大元素是第一个，任何集合都可以通过其迭代器以 O(1) 的时间复杂度访问它）。在这种情况下，您不必对其进行排序。

任何排序算法在输入已排序时至少需要 O(n) 的时间复杂度（当输入未排序时至少需要 O(nlog(n))），因为您不能在不遍历所有元素的情况下验证输入是否已排序。因此，排序算法无法击败您的 O(n) 解决方案。

- Eran

---

好的，由于我们事先不知道输入是否已排序，因此这将是解决它最有效的方法？ - chitresh sirohi

@chitreshsirohi 是的，如果不检查所有元素，就无法知道哪个元素最大。 - Eran

Answer 2

你的问题暗示了它自己的答案。这取决于集合本身的来源。也就是说，你对数据集了解得越多，就能更快地设计出启发式方法来得到所需的答案。

因此，如果你的列表已经排序，那么list[0]或list[len-1]将是最高的...

次要的答案也取决于“列表将被搜索的频率”。如果这是一次性搜索，那么只需遍历列表以找到最高值即可最快。 如果你将重复执行此操作（例如，收集各种指标），则首先对其进行排序，使用快速排序可能是最好的选择。

- cmroanirgo

Answer 3

使用Java 8，您可以使用Stream API查找max，但这并不能解决O(n)问题。然而，元素访问比普通迭代器的计算成本要低。

list.stream().mapToInt(i -> i).max().getAsInt();

- Laazo

Answer 4

你的问题是，如何在一个未排序的列表中找到最大值有两个选项。

选项1： 使用你在问题中提到的方法getHighestNumber

选项2： 使用世界上最有效的排序算法对列表进行排序，然后取列表的最后一个值。

那么从效率角度来看，哪个选项更好呢？

我的答案是：如果数组没有排序，那么没有任何排序算法能够超过选项1。

- hunter

Answer 5

这里是我最喜欢使用的一个论据，可以快速判断这样的问题：

你至少需要使用 O(N) 的时间来查看所有元素，这就是I/O时间。

没有太多思考，这可以让自己信服：在复杂性方面，任何算法都无法打败任何 O(N) 算法。希望这有意义。

- shole