Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
【思路1】java HashMap
我们用java的HashMap，把数组中的值做为键，把元素的数目作为值。如果出现了一个元素的数目大于nums.length/2，则返回该值。代码如下：
public class Solution {
public int majorityElement(int[] nums) {
if(nums.length==0 || nums==null) return 0;
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
if(map.containsKey(nums[i])){
if(map.get(nums[i])+1 > nums.length/2) return nums[i];
map.put(nums[i], map.get(nums[i])+1);
}
else
map.put(nums[i], 1);
}
return nums[0];
}
}
【思路2】
由于数组中肯定存在一个majority number。因此我们可以遍历数组，如果找到一对值不同的元素就把他们删除，那么最后剩下的一定majority number。这种算法叫Moore’s Voting Algorithm，由Robert S.Boyer 和J Strother Moore于1980年发明，是线性时间复杂度。
举个例子：[1,2,3,1,1,1] (1,2)是一对不相同的元素，(3,1)是另一对不相同的元素，那么剩下的1肯定是majority number。代码如下：
public class Solution {
public int majorityElement(int[] nums) {
if(nums.length==0 || nums==null) return 0;
int count = 0;
int result = 0;
for(int i = 0; i < nums.length; i++){
if(count == 0){
result = nums[i];
count = 1;
}
else{
if(nums[i] == result){
count ++;
}
else count --;
}
}
return result;
}
}
当然，这种算法对于存在主元素的数组是有效的，如： A A A C C B B C C C B C C
它肯定能返回主元素C。但是，如果不存在主元素，那么得到的结果就跟遍历顺序有关了。如: A A A C C C B
如果是从左到右，那么结果是B，如果是从右到左，那么结果是A。