主元素1：
这道题是编程之美上的一道原题，如果题目未对时间复杂度有严格要求的话可以先排序，再取中位数。
本题中要求算法达到时间复杂度为O(n)，空间复杂度为O(1)，算法如下：
public int majorityNumber(ArrayList<Integer> nums) {
int count = 0;
int mainElement = -1;
for(int i = 0; i < nums.size(); i++){
if(count == 0){
count = 1;
mainElement = nums.get(i);
} else if(mainElement == nums.get(i)){
count ++;
} else{
count --;
}
}
return mainElement;
}
基本思想是每次删除使两个不同的数字两两“抵消”，每次剩下的元素中主元素的次数仍然应该超过总个数的一半，不断重复此过程。
这个过程如果觉得不好理解的话，我在牛客网看到一个简单易懂的解释：第一个数字作为第一个士兵，守阵地；count = 1； 遇到相同元素，count++；遇到不相同元素，即为敌 人，同归于尽,count--； 当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，则可能是主元素。
主元素2：
给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的三分之一。
这道题并没有好的思路。简单的用哈希表统计每个数字出现的次数，在遍历哈希表找到符合要求的数字。时间复杂度O(n)，空间复杂度O(n)。
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i < nums.size(); i++){
if(!map.containsKey(nums.get(i))){
map.put(nums.get(i),1);
} else {
Integer count = map.get(nums.get(i));
map.put(nums.get(i), ++count);
}
}
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
if(entry.getValue() > nums.size()/3){
return entry.getKey();
}
}
return 0;
}