数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例

• 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
• 输出: 2

限制

• 1 <= 数组长度 <= 50000

方法： 哈希表

我们创建一个哈希表用来统计每个元素出现的次数，当循环遍历数组的时候，如果当前元素出现的次数大于目标数组的长度的一半，立即返回该元素即可。

代码如下：

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(n)。

方法：数组排序

如果将数组中所有元素进行顺序排序，那么数组中间的元素一定是众数。

代码如下：

复杂度分析

• 时间复杂度：O(nlogn)。将数组排序的时间复杂度为 O(nlogn)。
• 空间复杂度：O(logn)。

方法：摩尔投票法

Boyer-Moore majority vote algorithm，该算法解决的问题是如何在任意多的候选人（选票无序），选出获得票数最多的那位。

• 维护一个众数和他出现的次数。
• 遍历数组中的所有元素，如果次数为 0，我们就把众数赋值为当前值。
• 如果众数等于当前值，次数加 1；否则减 1；
• 遍历完整个数组后，最后统计的众数即为整个数组的众数。

代码如下：

复杂度分析

• 时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
• 空间复杂度：O(1)。Boyer-Moore 算法只需要常数级别的额外空间。

END

水滴集多成大海，读书集多成学问，赠友人。

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。