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.
题目标签：Array
忘记说了，特地回来补充，今天看完《中国有嘻哈》 复活赛，Jony J 回来了！ 特激动！ 一开始看的时候就喜欢他，虽然他忘词两次被淘汰！但是实力终究是在的，一挑五 荣耀回归！
知道他消失好多集肯定是当不了冠军了！ 但是呢，他回来可以让更多的人有机会听到他好听的歌，就足够了！ Respect！ 推荐给大家 《不用去猜》和《套路》，写code 也要劳逸结合嘛，迷茫的时候听听，他的歌挺正能量的。
题目给了我们一个array，里面必定会有一个众数，让我们找出众数。
利用Moore Voting 摩尔投票法，设定一个count，和一个result，遍历nums array， 当count 等于0 的时候，把result 等于 当前的数字，更新count = 1；
当遇到重复的数字时候，count++；
当遇到不重复的数字时候，count--。
因为众数的数量肯定大于nums array一半的数量，所以遍历完之后，不管它怎么++ --， 众数的数量肯定够其他的数字减，而且还有的剩，所以剩下的就是众数。
Java Solution:
Runtime beats 82.86%
完成日期：04/06/2017
关键词：Array
关键点：Moore Voting，众数的特性是数量 大于 总数的一半
import java.util.Hashtable;
public class Solution
{
public int majorityElement(int[] nums)
{
// if there is only 1 or 2 numbers in array, nums[0] is the majority since there must have majority.
if(nums.length == 1 || nums.length == 2)
return nums[0]; int result = 0;
int count = 0;
// iterate the array
for(int i=0; i<nums.length; i++)
{
if(count == 0) // if count = 0, meaning start over from current one. The previous are cancel out.
{
result = nums[i];
count = 1;
}
else if(result == nums[i])
count++; // if the number is repeated, increase count.
else
count--; // if the number is not repeated, decrease count.
} // the leftover number must be the majority one since it appears more than half.
return result;
}
}
参考资料：
http://www.cnblogs.com/grandyang/p/4233501.html
LeetCode 算法题目列表 - LeetCode Algorithms Questions List