題目

數組中占比超過一半的元素稱之為主要元素。給你一個 整數 數組，找出其中的主要元素。若沒有，返回 -1 。請設計時間復雜度為 O(N) 、空間復雜度為 O(1) 的解決方案。

示例 1：

輸入：[1,2,5,9,5,9,5,5,5]
輸出：5
示例 2：

輸入：[3,2]
輸出：-1
示例 3：

輸入：[2,2,1,1,1,2,2]
輸出：2

解題思路

摩爾投票理解

對于[1,2,5,9,5,9,5,5,5]，主要元素為5，可以想象成元素被分成了兩撥，一波是主要元素，一波是非主要元素。
假設元素之間兩兩相互抵消

• 在最壞的情況下，所有非主要元素和主要元素兩兩相互抵消，最后應該會剩下一個主要元素
• 在最好情況下，非主要元素之間互相殘殺，先把非主要元素內部的元素盡量抵消掉，然后再去與主要元素抵消，最后剩下的主要元素>1
• 所以即使在最壞的情況下，仍然最少會剩下一個主要元素的
• 所以我們假設主要元素是can，cnt代表can元素與非主要元素抵消后，can元素還剩多少個，當cnt==0時，說明當前的can元素已經被全部抵消掉了，需要重新設定新的can元素
• 因為使用can記錄了當前主要元素，所以可以防止相同元素之前互相殘殺

代碼

class Solution {public int majorityElement(int[] nums) {int can=-1,cnt=0,res=0;for (int num : nums) {if(cnt==0){can=num;}if(num==can){cnt++;}else {cnt--;}}for (int num : nums) {if(num==can)res++;}return res>=(int)(Math.floor((double)nums.length/2)+1)?can:-1;}
}