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.

 思路：给一个大小为n的一维数组，找到里面出现次数最多的数字。出现最多的元素的意思是在数组中出现超过一半的次数。

最暴力的算法是对数组进行排序，然后输出中间的数字。

代码如下：

int majorityElement(vector
     
      & nums) {        sort(nums.begin(), nums.end());        return nums[nums.size() / 2];    }
     

但是这种算法的时间复杂度会比较大。

优秀的代码是投票的方式：Every number in the vector votes for itself, the majority number gets the most votes. Different number offsets the votes.，每个数字对自己进行投票，出现次数最多的元素将会得到最多的票数，不同的数字之间会抵消投票。

具体代码如下：

int majorityElement(vector
     
       &num) {        int vote = num[0];    int count = 1;    int size = num.size();    //vote from the second number    for( int i = 1; i < size; i++ )    {        if( count == 0 ) { vote = num[i]; count++; }        else if( vote == num[i] )    count++;        else count--;    }    return vote;    }
     

参考资料：https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html