为什么使用排序查找多数元素要比使用哈希映射更快？

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

Array.sort（）函数是使用quicksort在jave中实现的，并且具有O（nlgn）时间复杂度。

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

因此，solution 1（Sorting）应该比solution 2（Hashmap）花更多的时间，但是当我对Leetcode进行问题时，解决方案2消耗的平均时间要长得多（几乎是解决方案1的8倍。

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

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

Answer 1

以周期来衡量算法并不一定要得出时间消耗，但是您的假设是正确的，哈希映射（在最佳情况下）应该需要更少的周期。但是：在启用任何形式的并行性方面，这一切都更加令人困惑。

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

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

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

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

Answer 2