leetcode 众数

Q

https://leetcode.cn/problems/majority-element/description/

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

A

Hash Table Count the number of appearances for each distinct number in nums, once we see a number appear more than n / 2 times, it is the majority element.

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

Sorting Since the majority element appears more than n / 2 times, the n / 2-th element in the sorted nums must be the majority element. In this case, a partial sort by nth_element is enough.

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

Randomization Pick an element randomly and check whether it is the majority one.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n=nums.size();
        int gate=n/2;
        while(true){
            int pos=(((double)rand())/RAND_MAX)*n;
            int num=nums[pos];
            if(count(nums.begin(),nums.end(),num)>gate)
                return num;
        }
        return 0;
    }
};

Divide and Conquer Recursively find the majority in the two halves of nums and combine the results. The base case is that the majority element of a single-element array is just that element.

nlg(n)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        return majority(nums, 0, nums.size() - 1);
    }
private:
    int majority(vector<int>& nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }
        int m = l + (r - l) / 2, lm = majority(nums, l, m), rm = majority(nums, m + 1, r);
        if (lm == rm) {
            return lm;
        }
        return count(nums.begin() + l, nums.begin() + r + 1, lm) > count(nums.begin() + l, nums.begin() + r + 1, rm) ? lm : rm;
    }
};

Moore Voting Algorithm

众数最终一定会打败其他可能是众数的数字

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int counter = 0, majority;
        for (int num : nums) {
            if (!counter) { // check counter before update counter: 如果counter等于0，说明之前的所有可能的众数都打平了，可以重新开始一个
                majority = num;
            }
            counter += num == majority ? 1 : -1;
        }
        return majority;
    }
};

Bit Manipulation The bits in the majority are just the majority bits of all numbers.

众数的某bit如果是0，则所有数的这一位的bit为0的数目会>一半，从而bit为1的数目会小于一半

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int majority = 0;
        for (unsigned int i = 0, mask = 1; i < 32; i++, mask <<= 1) { // 使用无符号类型作为mask，因为有符号类型移位宽度位的时候是未定义的
            int bits = 0;
            for (int num : nums) {
                if (num & mask) {
                    bits++;
                }
            }
            if (bits > nums.size() / 2) {
                majority |= mask;
            }
        }
        return majority;
    }
};