Majority Element

文章目录

题目求一组数组中的众数。所谓众数就是该元素在数组中出现的次数超过⌊n/2⌋次。

最简单也最容易想到的方法就是对整个数组进行排序，因为众数的概念使得在排好序后的数组中间的数肯定为众数，但是这个方法的时间复杂度是O(nlogn)的，我们可以有更快的方法。

对整个数组建立一个映射，键是数组中出现过的元素，值为这些元素出现的次数。那么这个方法的时间复杂度是O(n)，效率上比排序的方法要好了，但是却牺牲了空间，因为需要O(n)的空间里实现映射。

那么还有更好的方法吗？

从头到尾扫一遍数组，用一个变量cnt来记录出现次数，如果该数和“当前假定的众数”（只是暂时的，可能因为在遍历的过程中发现比它更大的众数）相同，cnt就加1，不同就减1。当cnt变为0的时候，更新这个“当前假定的众数”，因为有更大的众数把我们假定是众数的数给覆盖了。

这个方法的时间复杂度是O(n)，空间复杂度只有O(1)。

注：这里题目假设了输入的矩阵不为空而且肯定存在众数。