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.

 

思路：

找主要元素，用major记录主要字母，n记录major相对于其他字母多出现的次数

if         n == 0 ， 设当前数字为主要数字

else if   当前数字等于主要数字， n++

else     当前数字不等于主要数字， n--

 

因为主要数字出现多于一半，所以最后major表示的一定是主要数字。

没测试就一次AC了 

class Solution {public:    int majorityElement(vector
     
       &num) {        int major;        int n = 0;        for(int i = 0; i < num.size(); i++)        {            if(n == 0)            {                major = num[i]; n++;            }            else if(major == num[i])            {                n++;            }            else            {                n--;            }        }        return major;    }};