169.Majority Element

Tags: Easy Array Divide and Conquer Bit Manipulation

Links: https://leetcode.com/problems/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

---

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，所以排序后下标为n/2的一定就是众数。

---

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;
    }
};

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

---

位运算的方法思路比较新奇，因为考虑到最后的结果是一个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;
    }
};