229. 求众数II，摩尔投票O(n)

18 Mar 2020

预计阅读时间 ~10 分钟

摩尔投票算法

作者：喝七喜链接：https://www.zhihu.com/question/49973163/answer/235921864 来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

首先请考虑最基本的摩尔投票问题，找出一组数字序列中出现次数大于总数1/2的数字（并且假设这个数字一定存在）。显然这个数字只可能有一个。摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。请首先认同这个事实，这里不证明了~

所以我们的目标就是：删除，删除，删除。删到不能删除为止。 实现的算法从第一个数开始扫描整个数组，有两个变量(参考第一答题者的变量名)major和count。其实这两个变量想表达的是一个 “隐形的数组”array，array存储的是“当前暂时无法删除的数字” ，我们先不要管major和count，只考虑这个array，同时再维护一个结果数组result，result里面存储的是每次删除一对元素之后的当前结果 。

为了方便理解举一个示例输入：{1,2,1,3,1,1,2,1,5}

从第一个数字1开始，我们想要把它和一个不是1的数字一起从数组里抵消掉，但是目前我们只扫描了一个1，所以暂时无法抵消它，把它加入到array，array变成了{1}，result由于没有抵消任何元素所以还是原数组{1,2,1,3,1,1,2,1,5}。
然后继续扫描第二个数，是2，我们可以把它和一个不是2的数字抵消掉了，因为我们之前扫描到一个1，所以array变成了{},result变成了 {1,3,1,1,2,1,5} (1被2抵消掉了)
继续扫描第三个数1，无法抵消，于是array变成了{1},result还是{1,3,1,1,2,1,5};
接下来扫描到3,可以将3和array数组里面的1抵消,于是array变成了{},result变成了{1,1,2,1,5}
接下来扫描到1，此时array为空，所以无法抵消这个1，array变成了{1},result还是{1,1,2,1,5}
接下来扫描到1，此时虽然array不为空，但是array里也是1，所以还是无法抵消，把它也加入这个array,于是array变成了 {1,1}（其实到这我们可以发现，array里面只可能同时存在一种数，因为只有array为空或当前扫描到的数和array里的数字相同时才把这个数字放入array）,result还是{1,1,2,1,5}
接下来扫描到2，把它和一个1抵消掉，至于抵消哪一个1，无所谓，array变成了{1},result是{1,1,5}
接下来扫描到1，不能抵消，array变成了{1,1}，result{1,1,5}
接下来扫描到5，可以将5和一个1抵消，array变成了{1},result变成了{1}
至此扫描完成了数组里的所有数，result里剩了1，所以1就是大于一半的数组。

再回顾一下这个过程，其实就是删除（抵消）了（1，2），（1，3），（1，5）剩下了一个1。 除去冗余关系：实际代码中没有array，也没有result，因为我们不需要。 由于前面提到array里只可能同时存储一种数字，所以我们用major来表示当前array里存储的数，count表示array的长度,即目前暂时无法删除的元素个数，最后扫描完所有的数字，array和result变成一样了，都表示“最后还是无法删除的数字”。

其实就是把需要被抵消掉的数字加入虚拟数组。因为虚拟数组里的元素相同，所以用2个变量压缩数组。(major为元素，count为次数) 遍历数组时，会遇到3种情况：

如果虚拟数组为空，那么就加入虚拟数组，成为需要被抵消的数字； (major=num, count=1)
否则，如果跟虚拟数组里的元素相同，那么扩展虚拟数组（++count）;
否则，把当前元素跟虚拟数组里的元素进行抵消删除（–count）；

class Solution {
    public int majorityElement(int[] nums) {
        int majorNum = 0, cnt = 0;
        for (int num: nums) {
            if (num == majorNum) ++ cnt; // 加入虚拟数组（当前无法删除的元素）
            else if (cnt == 0) { // 无法抵消，加入虚拟数组
                majorNum = num;
                cnt = 1;
            } else -- cnt; // 抵消掉虚拟数组里的一个元素
        }
        return majorNum;
    }
}

找出数组里所有出现超过 n/3 次的元素

这种元素最多只有2个，因为可以想象 把数组分成相等的三部分 ，其中 2部分只包含有1个元素 ，第3部分包含1到多个前两部分的元素和其他的一些元素。

所以使用2个虚拟数组，用摩尔投票找出数组里出现次数前2大的元素。每次删除3个不同的元素，剩下的元素就可能是超过n/3元素（边界条件为只有一个解/没有解的数据）。

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int num1 = 0, num2 = 0;
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (num1 == nums[i]) {
                ++ cnt1;
            } else if (num2 == nums[i]) {
                ++ cnt2;
            } else if (cnt1 == 0) {
                cnt1 = 1;
                num1 = nums[i];
            } else if (cnt2 == 0) {
                cnt2 = 1;
                num2 = nums[i];
            } else {
                -- cnt1;
                -- cnt2;
            }
        }

        List<Integer> ans = new ArrayList<Integer>();
        cnt1 = 0;
        cnt2 = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == num1) ++ cnt1;
            else if (nums[i] == num2) ++ cnt2;
        }
        if (cnt1 > nums.length/3) {
            ans.add(num1);
        }
        if (cnt2 > nums.length/3) {
            ans.add(num2);
        }
        return ans;
    }
}