多数元素问题:
给定大小为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是否会变得更有效率?
软件工程师必须同时考虑实际性能和实际极限性能。例如,从理论上讲,哈希映射查找比未排序的数组查找要快...但是,由于额外的代码复杂性,大多数数组很小(10-100个元素),没有任何O(n)优势。
您当然可以稍微优化一下代码,但是在这种情况下,除非引入其他因素(例如,人为地减慢一个常数的时间,否则除非您引入其他因素,否则您不可能将n的结果更改为小)。
((我想找到一个很好的比喻来说明,但是比预期的要难...)
为什么?最坏情况下的[[Solution 1受让人
O(N log 2 N),但是HashMap O(N。(M + R ))其中M是冲突的代价,R是调整数组大小的代价。
HashMap在内部使用节点的名为table
的数组,并且当输入增加或缩小时,它会调整不同时间的大小。并且您为其分配了初始容量100。所以让我们看看会发生什么? Java使用单独的链接来解决冲突,并且某些测试用例可能会有很多冲突,这会导致查询或更新哈希图时花费大量时间。Conclusion哈希图的实现受两个因素影响:1.根据输入大小调整表数组的大小。2.输入中出现多少个冲突
因此,我建议您首先更改您的方法#2并为其提供一个Hashmap进行搜索,而不是在要测量的函数中构建它。
我不太确定您是如何停止时间的,但这也是一种想法:
为了进行实时比较,您应该使用带时间戳的记录器,或者使用Java中测量执行时间的常用技术(因为java8即Instant.now()可以将时间打印到控制台)。