[数据结构与算法]数组中出现次数超过一半的数字

最简单的哈希表

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

摩尔投票法

初级版

摩尔投票的思想本质上像是无限大乱斗，两个数只要不是完全一样的就给它抵消掉，最后剩下来的就是绝对多数

想象着这样一个画面：会议大厅站满了投票代表，每个都有一个牌子上面写着自己所选的候选人的名字。然后选举意见不合的（所选的候选人不同）两个人，会打一架，并且会同时击倒对方。显而易见，如果一个人拥有的选票比其它所有人加起来的选票还要多的话，这个候选人将会赢得这场“战争”，当混乱结束，最后剩下的那个代表（可能会有多个）将会来自多数人所站的阵营。但是如果所有参加候选人的选票都不是大多数（选票都未超过一半），那么最后站在那的代表（一个人）并不能代表所有的选票的大多数。因此，当某人站到最后时，需要统计他所选的候选人的选票是否超过一半（包括倒下的），来判断选票结果是否有效。

一个比较简单的方法是多次循环并删除对撞元素，直到无不相同元素为止

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int i = 0;
        while(i < nums.size()-1) {
            if (nums[i] != nums[i+1]) {
                nums.erase(nums.begin()+i, nums.begin()+i+2);
                if (i > 0) {
                    i--;
                }
            }
            else {
                i++;
            }
        }
        return nums[0];
    }
};

为了避免多次删除的耗时操作，可以用栈来记录

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        stack <int> repeatElement;
        for (int n: nums) {
            if (repeatElement.empty() || repeatElement.top() == n) {
                repeatElement.push(n);
            }
            else {
                repeatElement.pop();
            }
        }
        return repeatElement.top();
    }
};

升级版，直接用票数变量来记录

其实本质上和栈差不多，用counts来判断栈是否为空，cand对应栈顶元素

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cand = 0, counts = 0;
        for (int num: nums) {
            if (counts == 0) {
                counts++;
                cand = num;
            }
            else {
                if (num == cand) {
                    counts++;
                }
                else {
                    counts--;
                }
            }
        }
        return cand;
    }
};