Voting Algorithm

Majority Element

俄罗斯方块的消除方式。出现两个不一样的消除：counter 减一。

  • A
  • A B -> 消除
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (count == 0) {
                major = nums[i];
                count++;
            } else {
                count += (nums[i] == major)? 1 : -1;
            }
        }
        return major;        
    }
};

Majority Element II

同理：俄罗斯方块的消除方式，当出现三个不一样的时候消除。 要注意的是，最后得到的candidate，需要再过一遍数组来确定是不是最后的答案。

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int x = 0;
        int y = 1;
        //just need to be different test with case [0,0,0,0,0,0]
        int cnt1 = 0;
        int cnt2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == x) {
                cnt1++;
            } else if (nums[i] == y) {
                cnt2++;
            } else if (cnt1 == 0) {
                x = nums[i];
                cnt1++;
            } else if (cnt2 == 0) {
                y = nums[i];
                cnt2++;
            }  else {
                cnt1--;
                cnt2--;
            }
        }
        cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == x) {
                cnt1++;
            } else if (nums[i] == y) {
                cnt2++;
            }
        }
        vector<int> rst;
        if (cnt1 > nums.size() / 3) {
            rst.emplace_back(x);
        }
        if (cnt2 > nums.size() / 3) {
            rst.emplace_back(y);
        }
        return rst;
    } 
};

Majority Element III

More than 1/k