算法：数组中出现次数超过一半的数字

朱雀 2024-04-03 13:19 60阅读 0赞

![ff0a5738301653ea3ae85a49146bfa26.jpeg][]

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

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

## 示例 ##

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

## 限制 ##

*  1 <= 数组长度 <= 50000

## 方法：哈希表 ##

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

**代码如下：**

![3fb1632db6ac3b2b0a6cc8d8a9206ec7.jpeg][]

## 复杂度分析 ##

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

## 方法：数组排序 ##

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

![88cbd2fa39f8765a392178168dcb1a83.jpeg][]

**代码如下：**

![f0c76278e8c2847358db387764ffc431.jpeg][]

## 复杂度分析 ##

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

## 方法：摩尔投票法 ##

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

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

![d4a4769773ab193dfa63bc986d812823.jpeg][]

**代码如下：**

![e2cf40c6e2a98fa97d30165948bbfd69.jpeg][]

## 复杂度分析 ##

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

## END ##

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

[ff0a5738301653ea3ae85a49146bfa26.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/0b164c6f32d54f7c8d10b168e6a11f38.jpeg
[3fb1632db6ac3b2b0a6cc8d8a9206ec7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e5d5bf20cd1a4cc3b90ac711e980ca8d.jpeg
[88cbd2fa39f8765a392178168dcb1a83.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d841231ed9ef431daee3e5363e87092d.jpeg
[f0c76278e8c2847358db387764ffc431.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d85e1e95b01c40dcb8fc023c9990e710.jpeg
[d4a4769773ab193dfa63bc986d812823.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/6217533c8ace4705b38277193a4e313e.jpeg
[e2cf40c6e2a98fa97d30165948bbfd69.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/481bb8b5f8604476b23d619e21e763cd.jpeg