[LeetCode]Majority Element

这道题用sort和hashmap都可以做。但是Moore Voting是可以达到O(n)时间常数空间的解法。基本思想是，总共n个数，找出现大于n/2次数的数，我们每次消去不同的一队，如果存在这个数，剩下的那个数就是我们要找的。否则就不存在。所以我们通过moore voting找打那个数之后，还有去原数组验证一遍（[1,2,3]的情况，我们最后保留的数是3，但其不是众数）。如果要找出现次数大于n/3的数的话，因为最多有可能有两个这样的数，所以我们保留两个candidate，每次消去三个不同的数，最后回原数组验证，以此类推。这道题保证有结果，所以我们不需要去原数组验证，代码如下：