数学——众数

众数是一组数中出现频率最多的数，可以用unordered_map来统计从而求得答案，但是对于一个特殊的序列，众数的出现次数大于n/2，解决方法就会比较多了。

题面以LeetCode 169.Majority Element为背景：

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

---

排序法

排序的方法类似于求中位数的方法，因为出现次数最多的元素的数量大于n/2，所以排序后下标为n/2的一定就是众数。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        sort(nums.begin(), nums.end());
        int n = nums.size();
        return nums[n / 2];
    }
};

摩尔投票法

这种方法还是第一次遇到，但是有一个大前提就是众数的出现次数至少是n/2，叫做摩尔投票法（Moore Voting），核心思路是每次让两个不同的元素抵消掉，那么最后剩下的就是众数了，直观上比较好理解。在写算法的时候，可以不用真的删掉元素，而是用一个sign值来标记，如果是两个不同的元素，那么数值减1，当减到0的时候，让res为当前元素，标记sign增加1.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int sign = 0;
        int res = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (sign == 0) {
                res = nums[i];
                ++sign;
            }
            else {
                if (nums[i] == res) ++sign;
                else --sign;
            }
        }

        return res;
    }
};

位运算法

位运算的方法思路比较新奇，因为考虑到最后的结果是一个int类型的数，所以转而去检验每一位的1的个数，如果1的个数超过了n/2，那么这一位一定是1。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int res = 0;
        int n = nums.size();
        for (int i = 0; i < 32; ++i) {
            int one = 0, zero = 0;
            for (auto num : nums) {
                if (one > n / 2 || zero > n / 2) break;
                if (num & (1 << i)) ++one;
                else ++zero;
            }
            if (one > zero) res |= (1 << i);
        }

        return res;
    }
};