发病笔记-摩尔投票

229. 求众数 II

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

懒得跟着另外几篇题解复读一遍，而且leetcode没绑手机发不了帖，还是放B站做一个记录。

初见题目，首先想到的肯定是Hash map！(破音)  像这个：

然后击败了百分之10的用户。

直接看题解，得到关键字：摩尔投票。

然后就去维基看了下，发现了一个令人震惊的事实：

摩尔投票，摩尔定律，摩尔密码......这三个摩尔并不是同一个人。

震惊完回来看题解。摩尔投票的原理很简单：次数超过n/3次的元素最多只存在两个，先假设这两个元素真的存在。假设存在两个，那么把所有数字分成每三个一组，三个数字不同就“抵消”，最后一定会剩下那两个数字。

比如 1 6 3 5 5 5 6 6 5 6

任意分组，1 6 3 不同，全部抵消。 5 5 5一样，留下。6 6 5，把 5抵消。剩下不管。

最后剩5和6两个数字。

嘛......道理差不多就是这么回事，主要是代码的实现我没看懂。

没懂的地方是，count++的含义。于是换了思路，我要和自己以外的人战斗，另外的自己是同伴，遇到了同伴就增加了战斗的资本，遇到了敌人就战斗，敌人死掉，我也会死。如果我死了，那么剩下的同伴会继续战斗，如果一个我都没有了，那么我会被取代。

经历无数的厮杀后，活下来的就是天选之子，也就是答案。

世界还真是残酷啊。

其实是这样。一开始没懂count++的意义，因为原理那一块并没说要记录投票数。但其实可以这么理解，假设当前数字是i，count++实际上记录的i被分到了多少个组里......因为开始说了，每三个数字一组，不同的数字被抵消，相同的留下。当count++时，能被用于分组的i增加了，然后i被分到不同数字的组里就抵消了，当count==0，i用完了，再用新的数去分组(新的数字仍可能是i)。假设答案存在，那么它的出现次数是大于n/3的，然后又是三个数字一组，所以答案绝对不会被完全抵消，没被抵消完的就是答案。

世界真是太残酷了。