多数元素题解（LC：169）

 169. 多数元素
 

 核心思想（Boyer-Moore 投票算法）：

• 解题思路：可以使用 Boyer-Moore 投票算法、该算法的核心思想是：

  • 维护一个候选元素和计数器、初始时计数器为 0。

  • 遍历数组：

    • 当计数器为 0 时、设置当前元素为候选元素。

    • 如果当前元素等于候选元素、计数器加 1。否则、计数器减 1

  • 最终、候选元素即为多数元素。

思路类比：士兵打仗（两军对抗）

假设：

• 每个数是一名士兵、士兵可能来自甲军（候选元素）或乙军（非候选元素）。

• 每当我们遇到一个士兵：

  • 如果他是甲军、我们 +1。

  • 如果他是乙军、我们 -1（理解为与甲军一人同归于尽）。

• 一旦计数为0、说明甲军原来的优势被抵消了、我们重新选择当前的士兵作为新的候选（也就是新的甲军）。

由于题目保证多数元素存在（出现次数 > n/2）、那么无论中间怎样对冲、最后剩下的那个一定是甲军士兵（多数元素）。

class Solution {public int majorityElement(int[] nums) {int count = 0;int candidate = 0;for (int num : nums) {if (count == 0) {candidate = num;}if (num == candidate) {count++;} else {count--;}}return candidate;}
}

这个算法的时间复杂度是 O(n)、空间复杂度是 O(1)