多数元素问题：
给定一个大小为 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 花费的平均时间比解决方案 1多得多(几乎是 8 倍(。
为什么会这样呢？我真的很困惑.....
测试用例的大小是原因吗？当测试用例中的元素数量急剧增加时，解决方案 2 会变得更高效吗？
Big O不是实际性能的衡量标准。它只会让你了解与 n 相比，你的表现将如何演变。
实际上，对于某些 n，O(n.logn( 中的算法最终会比 O(n( 慢。但是这个n可能是1,10,10^6甚至10^600 - 在这一点上它可能无关紧要，因为你永远不会遇到这样的数据集 - 或者你没有足够的硬件来使用它。
软件工程师必须同时考虑实际性能和实际极限的性能。例如，哈希映射查找在理论上比未排序的数组查找更快......但是大多数数组都很小(10-100 个元素(，由于额外的代码复杂性，抵消了任何 O(n( 优势。
你当然可以稍微优化你的代码，但在这种情况下，你不太可能改变小n的结果，除非你引入另一个因素(例如，人为地减慢每个周期的时间与常数(。
(我想找一个好的比喻来说明，但这比预期的要难......
这取决于测试用例，一些测试用例在 HashMap 中会更快，而另一些则不会。
为什么？在最坏情况下的解决方案1受助者O(N log2N(，但哈希映射O(N .(M + R((其中 M 是冲突的成本，是调整数组大小的成本。
HashMap 在内部使用一个名为table的节点的数组，当输入增加或缩小时，它会调整不同的时间。您为其分配了初始容量 100。
那么让我们看看会发生什么？Java使用单独的链接来解决冲突，某些测试用例可能会有很多冲突，这会导致查询或更新哈希图时消耗大量时间。
结论哈希图的实现受两个因素影响：1. 根据输入大小调整表数组大小 2.输入中出现多少次碰撞