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

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支持随机访问或O(1)访问持有最大元素的末尾Collection- 如果最大的元素是第一个，任何集合都会让您O(1)通过其访问它）Iterator）。不过，在这种情况下，您不必对其进行排序。

至少O(n)在输入已排序时（至少O(nlog(n))在未排序时）才会进行任何排序，因为如果不遍历所有元素，就无法验证输入是否已排序。因此排序算法无法击败您的O(n)解决方案。