茴字的十种写法 LeetCode 169 Majority Element

排序

部分排序

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

主要用了STL里面的nth_element, Time Complexity O(n), space Complexity O(1)

全排序

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

sort函数来完成，Time: O(nlogn), Space: O(1)

计数

HashTable

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

c++中的hashtable 实现，unordered_map. Time: O(n), Space: O(n)

BST

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int, int> counts;
        for(const auto& num : nums){
            if(++counts[num] > nums.size() / 2) return num;
        }
        return -1;
    }
};

map实现， Time: O(nlogk) Space: O(n)

投票

Moore Vote

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int majority = nums.front();
        int cnt = 0;
        
        for(const auto& num : nums){
            if(num == majority) cnt++;
            else if(--cnt == 0){
                majority = num;
                cnt = 1;
            }
        }
        return majority;
    }
};

思想：利用主要成分出现次数大于一半，如果不同的数据之间相互抵消，那么由于主要部分的次数优势，最终剩余的一定是主要部分。

Time: O(n), Space: O(1)

Bit Vote

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int majority = 0;
        int len = nums.size();
        for(int i=0; i<32; i++){
            int cnt = 0;
            int mask = 1 << i;
            for(const auto& num : nums){
                if((num & mask) && (++cnt > len / 2)){
                    majority |= mask;
                    break;
                }
            }
        }
        return majority;
    }
};

将每个数考虑为2进制的形式，然后majority必然在每一位为1的时候都会出现过半次。因此就找出哪一位的1出现次数过半，然后加上这一位。需要注意的是，majority |= mask, 而不能是majority = num, 因为不同的数可能在某些位置上也有相同的二进制1.

Time: O(32 * n)

Space: O(1)

随机采样

Randomization

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        srand(time(nullptr));
        int len = nums.size();
        
        while(true){
            int index = rand() % len;
            int majority = nums[index];
            int cnt = 0; 
            // Check the choice
            for(const auto& num : nums){
                if(num == majority && ++cnt > len / 2) return num;
            }
        }
        
        return -1;
    }
};

有超过50%的几率选择到majority, 当然如果脸黑，可能需要选n/2次。

time(nullptr)这里使用nullptr更符合函数定义，函数中的参数是指针，虽然0也可以（C中的宏定义空指针为0）

这里不使用srand也没问题。这里的实现需要依赖输入有解，如果无解会死循环，所以也可以shuffle一下数组，然后挨个取，如果都取完了还没有结果，就返回，避免死循环。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int len = nums.size();
        random_shuffle(nums.begin(), nums.end());
        for(const auto& num : nums){
            int majority = num;
            int cnt = 0;
            for(const auto& item : nums){
                if(majority == item && ++cnt > len / 2) return item;
            }
        }
        return -1;
    }
};

这种实现可能会稍微慢一点。因为random_shuffle的执行也需要Linear。

Time: O(n)

Space: O(1)

分治

Divide and Conquer

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        return findMajority(nums, 0, nums.size() - 1);
    }
private:
    int findMajority(vector<int>& nums, int l, int r){
        if(l == r) return nums[l];
        int m = l + (r - l) / 2;
        int lm = findMajority(nums, l, m);
        int rm = findMajority(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;
    }
};

分治算法，实现的时候注意STL [), 前闭后开，所以要r+1, 而不是r.

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

这样做的好处是不需要重复查询，只查询没查询过的另一半即可。要比之前的快一些。

Time: T(n) = 2T(n/2) + O(n), T(n) = O(nlogn), by master theorem

Space: O(logn) 递归深度

茴字的十种写法 LeetCode 169 Majority Element

排序

计数

投票

随机采样

分治

Reference