leetcode 169. 多数元素 (C++ | hash | 快排 | 摩尔投票算法)

public:
    int majorityElement(vector& nums) {
        unordered_map counts;
        int ans = 0, cnt = 0;
        int n = nums.size();
        for(int i = 0; i < n; i ++) {
            counts[nums[i]] ++;
            if(counts[nums[i]] > cnt) {
                ans = nums[i];
                cnt = counts[nums[i]];
            }
        }
        return ans;
    }
};

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

摩尔投票算法「时间复杂度O(n)，空间复杂度O(1)」
我们根据在数组中出现次数将数字划分两类。
第一类，出现次数大于半数的数字，假设为x，也是要找的数字。
第二类，出现次数小于半数的数字，假设为y，出现次数小于半数的数字可能有很多种，因为具体是几不重要，我们可以统一设为y。
那么，x出现次数 - y出现次数 > 0。
因此，我们统计当前众数x，和x众数出现的次数count，遇到一个y，将count–；如果count=0，说明当前没有数字是众数；如果当前数字等于x，那么将count++。因为众数一定存在，所以最后x即为众数且count>0。 leetcode 官方题解

class Solution {
public:
    int majorityElement(vector& nums) {
        int count = 0, x = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (count == 0) x = nums[i], count++;
            else if (nums[i] == x) count++;
            else count--;
        }
        return x;
    }
};