从整数集合中获取最高数的最有效方法

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;
    }

我的问题是，“对于给定的输入(例如，集合是否已经排序)，任何排序算法都能超过它(在时间尺度上)吗？”还有比这更好的方法吗？

Answer 1

如果集合已经排序，您可以在O(1)中找到最大的元素(假设Collection支持对持有最大元素的Collection结束的随机访问或O(1)访问--如果最大的元素是第一个，则任何集合都将通过其Iterator向您提供对它的O(1)访问)。不过，在这种情况下，你不必对其进行分类。

在对输入进行排序时，任何排序都至少需要O(n) (如果没有排序，则至少需要O(nlog(n)) )，因为您无法在不遍历所有元素的情况下验证输入是否已排序。因此，排序算法不能超过您的O(n)解决方案。

Answer 2

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

所以，如果您的列表已经排序，那么列表或listlen-1将是最高的.

第二个答案也取决于‘每隔多长时间搜索一次？’。如果这是一个一次性的搜索，那么仅仅迭代最高的列表将是最快的。如果您要重复进行(例如，收集各种度量)，那么首先使用快速排序对其进行排序，这可能是您最好的选择。

Answer 3

您的问题是，有两个选项可以找到未排序列表的最大值。

选项1:使用问题getHighestNumber中提到的方法

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

那么，在效率方面，什么是最好的选择。

我的答案是:选项1，如果数组没有排序，任何排序算法都不能超过选项1。