?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)