【LeetCode】169.多数元素

题目连接：
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;
    }
};