题⽬描述

数组中有⼀个数字出现的次数超过数组⻓度的⼀半，请找出这个数字。例如输⼊⼀个⻓度为 9 的数组 {1,2,3,2,2,2,5,4,2} 。由于数字 2 在数组中出现了 5 次，超过数组⻓度的⼀半，因此输出 2 。如果不存在则输出 0 。

思路及解答

哈希表法（HashMap）

哈希表法通过统计每个数字的出现次数来解决问题。遍历数组时，使用哈希表记录每个数字出现的次数，一旦发现某个数字的出现次数超过数组长度的一半，立即返回该数字。

  • 时间复杂度​：O(n)，其中 n 是数组的长度。我们只需遍历数组一次。

  • ​空间复杂度​：O(n)，最坏情况下需要存储所有不同的数字。

排序法

排序法的思路非常巧妙：​由于多数元素的数量超过数组长度的一半，那么将数组排序后，中间位置的元素一定是多数元素。

摩尔投票法（Boyer-Moore Voting Algorithm）

  1. 如果使⽤ hashmap 直接统计，需要额外的空间，我们不希望使⽤额外空间;

  2. 如果使⽤排序之后再统计，需要时间复杂度为O(nlogn)， 我们希望时间复杂度更低⼀点。

摩尔投票法是一种高效且空间复杂度低的算法。其核心思想是通过票数的抵消来找出多数元素。算法维护一个候选众数 candidate 和其票数 count。遍历数组时，若 count 为0，则选择当前数字作为候选；若当前数字与候选相同，则票数加1，否则减1。

核心逻辑就是采用“一换一抵消”的策略。因为真正的多数元素数量比其他所有元素加起来还要多，所以无论怎么相互抵消，最后剩下的那个候选者一定是它。

  • 时间复杂度​：O(n)，只需遍历数组两次（一次投票，一次验证）。

  • ​空间复杂度​：O(1)，只使用了常数个额外变量

注意，摩尔投票法的局限性：

  1. 摩尔投票法 只能找到绝对众数（也就是超过一半的数）

  2. 如果数组中没有任何一个元素的出现次数超过一半（例如 [1, 2, 3]），算法依然会返回一个结果（比如 3），但这个结果是错误的。因此，必须增加第二次遍历进行验证，确认该候选者的真实出现次数是否真的超过了半数。

  3. 基础的摩尔投票法只能找一个。如果需要找出现次数超过 n/3 的元素（最多有两个），需要使用摩尔投票法的扩展版（维护两个候选人和计数器），而不能直接用基础版。