题目连接：
https://leetcode.cn/problems/majority-element/solutions/2362000/169-duo-shu-yuan-su-mo-er-tou-piao-qing-ledrh/?envType=study-plan-v2&envId=top-interview-150

题目描述：

思路一：

使用哈希表unordered_map记录每个元素出现的次数，当满足条件时返回即可

代码：
时间复杂度O(n)
空间复杂度O(n)

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

思考：有什么方法可以将空间复杂度将到O(1)呢？

摩尔投票算法：

• 核心思想是抵消原则，在一个数组中如果某一个元素超过了一半，那么这个元素与其他元素一一配对，最后至少剩下一个该元素。

算法详解： https://leetcode.cn/problems/majority-element/solutions/2362000/169-duo-shu-yuan-su-mo-er-tou-piao-qing-ledrh/

时间复杂度O(N)
空间复杂度O(1)

代码实现：

class Solution {
public:int majorityElement(vector<int>& nums) {int x = 0, votes = 0;for (int num : nums){if (votes == 0) x = num;votes += num == x ? 1 : -1;}return x;}
};