题目：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例：

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2

思路一：

哈希统计元素出现次数

思路二：

先排序，排序后数组的最中间元素就是结果。

思路三：

摩尔投票，模拟投票更新过程，选票张数最多的人获胜。

依次遍历元素，记录当前获胜元素和选票张数vote；

如果vote为0，那么下一个元素作为暂时获胜元素；

如果vote不为0，那么比较当前获胜元素和当前遍历元素:如果相同，那么vote加1，如果不同，那么vote减1。

代码一：

class Solution {public:    int majorityElement(vector<int>& nums) {        unordered_map<int, int> mp;        int n = nums.size();        for(auto& val: nums)        {            mp[val]++;            if(mp[val] > n/2)                return val;        }        return INT_MIN;    }};

代码二：

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

代码三：

class Solution {public:    int majorityElement(vector<int>& nums) {        int result=INT_MIN;        int vote=0;        for(auto& val: nums)        {            if(vote==0)            {                result=val;                vote++;            }else            {                if(val == result)                {                    vote++;                }else                    vote--;            }        }        return result;    }};