Leetcode 169 - Majority Element（Moore投票算法）

题意

给一个数组，求它的majority，对majority的定义为：出现次数超过⌊n2⌋$/lfloor /frac{n}{2} /rfloor$的元素。

思路

算法1

O(nlogn)$O(nlogn)$时间。

排序，然后返回中间的那个元素即可。

算法2

O(n)$O(n)$时间和O(n)$O(n)$空间。

我们用unordered_map来存储每个元素出现的次数，最后返回出现次数超过⌊n2⌋$/lfloor /frac{n}{2} /rfloor$的元素即可。

算法3

我们能否将空间继续优化到const呢？答案是肯定的。

假设我们令我们的majority元素的数目为y，其他元素的个数为x，因为y>⌊n2⌋$y > /lfloor /frac{n}{2} /rfloor$。所以，一定有y−x>0$y - x > 0$。也就是说：平均情况下，至少每两个数会出现一个y。

那么，我们可以用一个cnt来记录y出现的次数，但是此时我们并不知道y是多少？那么我们假设任意一个元素z$z$为我们的majority，然后此时的cnt记为1。然后继续去遍历数组，假设当前遇到的元素为x$x$：

最后得到的z就是我们的majority。

然后刚刚查了一下，发现这个算法叫做Moore投票算法。

代码