为什么使用排序比使用HashMap更快地找到多数元素？

Question

多数元素问题：

给定大小为n的数组，找到多数元素。多数元素是出现超过⌊n / 2⌋次的元素。 您可以假设数组为非空，并且多数元素始终存在于数组中。

// Solution1 - Sorting ----------------------------------------------------------------
    class Solution {
        public int majorityElement(int[] nums) {
            Arrays.sort(nums);
            return nums[nums.length/2];
        }
    }

// Solution2 - HashMap ---------------------------------------------------------------
class Solution {
    public int majorityElement(int[] nums) {
        // int[] arr1 = new int[nums.length];
        HashMap<Integer, Integer> map = new HashMap<>(100);  
        Integer k = new Integer(-1);
        try{
            for(int i : nums){
                if(map.containsKey(i)){
                    map.put(i, map.get(i)+1);
                }
                else{
                    map.put(i, 1);
                }
            }
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
                if(entry.getValue()>(nums.length/2)){
                    k = entry.getKey();
                    break;
                }
            }
        }catch(Exception e){
            throw new IllegalArgumentException("Error");
        }
        return k;    
    }
}

Arrays.sort（）函数是使用QuickSort在Java中实现的，并且具有O（n log n）时间复杂度。

另一方面，使用HashMap查找多数元素仅具有O（n）时间复杂度。

因此，解决方案1（排序）应该比解决方案2（HashMap）花费更长的时间，但是当我在LeetCode上进行问题时，解决方案2花费的平均时间要多得多（将近8倍于解决方案1。

为什么会这样？我真的很困惑.....

测试用例的大小是原因吗？当测试用例中的元素数量急剧增加时，解决方案2是否会变得更有效率？

Answer 1

为什么？最坏情况下的[[Solution 1受让人

O（N log 2 N），但是HashMap O（N。（M + R ））其中M是冲突的代价，R是调整数组大小的代价。

HashMap在内部使用节点的名为table的数组，并且当输入增加或缩小时，它会调整不同时间的大小。并且您为其分配了初始容量100。所以让我们看看会发生什么？ Java使用单独的链接来解决冲突，并且某些测试用例可能会有很多冲突，这会导致查询或更新哈希图时花费大量时间。

Conclusion哈希图的实现受两个因素影响：1.根据输入大小调整表数组的大小。2.输入中出现多少个冲突

Answer 2

这就是说，让我们看一下这些功能的时间消耗。 （如果需要，我会在稍后添加时间戳。）您的函数不仅要评估数据，函数1可以简单地使用该初始化数组，而函数2必须创建该Map才能与给定的名称一起使用甚至在评估该算法之前就开始收集数据。

因此，我建议您首先更改您的方法＃2并为其提供一个Hashmap进行搜索，而不是在要测量的函数中构建它。

我不太确定您是如何停止时间的，但这也是一种想法：

为了进行实时比较，您应该使用带时间戳的记录器，或者使用Java中测量执行时间的常用技术（因为java8即Instant.now（）可以将时间打印到控制台）。

Answer 3

软件工程师必须同时考虑实际性能和实际极限性能。例如，从理论上讲，哈希映射查找比未排序的数组查找要快...但是，由于额外的代码复杂性，大多数数组很小（10-100个元素），没有任何O（n）优势。

您当然可以稍微优化一下代码，但是在这种情况下，除非引入其他因素（例如，人为地减慢一个常数的时间，否则除非您引入其他因素，否则您不可能将n的结果更改为小）。

（（我想找到一个很好的比喻来说明，但是比预期的要难...）