169.多数元素（摩尔投票法）

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

看到这个题目第一想法就是先排序，把多数元素先聚成一堆，由于多数元素出现的次数大于二分之n，所以n/2的位置一定是多数元素

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

ps:因为c++排序的时候可以直接sort，而c中用qsort还要写个比较函数，所以当我遇到要用到排序的时候我一般都会用c++

做完之后去看了看官方的题解，发现了种没见过的解法------摩尔投票法

具体原理解释为：

1. 如果候选人不是maj 则 maj,会和其他非候选人一起反对 会反对候选人,所以候选人一定会下台(maj==0时发生换届选举)
2. 如果候选人是maj , 则maj 会支持自己，其他候选人会反对，同样因为maj 票数超过一半，所以maj 一定会成功当选

int majorityElement(int* nums, int numsSize)
{
    int candidate = -1;   //这边candidate可以为任何数
    int count = 0;
    for(int i = 0;i < numsSize;i ++)
    {
        if(count == 0)
        {
            candidate = nums[i];
            count ++;
        }
        else if(nums[i] == candidate)
        {
            count ++;
        }
        else
        {
            count --;
        }
    }
    return candidate;
}

还是感觉挺神奇的，但我还是选择用排序o(*￣▽￣*)o