題目描述
給定一個大小為 n 的數組 nums ，返回其中的多數元素。多數元素是指在數組中出現次數 大于 ? n/2 ? 的元素。
你可以假設數組是非空的，并且給定的數組總是存在多數元素。
題目解法
博耶-摩爾多數投票算法（英語：Boyer–Moore majority vote algorithm）,中文常作多數投票算法、摩爾投票算法等，是一種用來尋找一組元素中占多數元素（出現次數??超過一半??的元素）的空間復雜度O(1)、時間復雜度O(n)算法。
該算法基于一個關鍵的觀察：??多數元素的出現次數大于其他所有元素出現次數之和??。它通過一種“??對抗抵消??”的策略來工作：
- 將數組中的不同元素視為互相“抵消”。
- 由于多數元素的數量占絕對優勢，無論怎么抵消，最后剩下的一定是多數元素。
通俗的說，可以將其想象成一場選舉：
- 數組中的每個元素都是一張選票。
- 算法維護一個候選人（candidate）和該候選人當前的票數（votes）。
- 遍歷過程中，支持當前候選人的票會增加票數，反對票則減少票數。
- 當票數歸零時，意味著當前候選人沒有任何優勢，于是更換新的候選人。
- 由于多數元素的存在，最后獲選的候選人一定是多數元素。
class Solution {public int majorityElement(int[] nums) {int n = nums.length;int candidate = 0, votes = 0;for (int i = 0; i < n; i++) {if (votes == 0) {candidate = nums[i];votes = 1;} else if (nums[i] == candidate) {votes++;} else {votes--;}}return candidate;}
}
