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)