題意

給一個數組，求它的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投票算法。

代碼