給定一個大小為?n?的數組，找出其中所有出現超過?? n/3 ??次的元素。

說明: 要求算法的時間復雜度為 O(n)，空間復雜度為 O(1)。

示例?1:

輸入: [3,2,3]
輸出: [3]
示例 2:

輸入: [1,1,1,3,3,2,2,2]
輸出: [1,2]

思路：

摩爾投票法

超過n/3，那可能的眾數個數為0，1，2

先假設兩個值為眾數，開始遍歷數組

如果發現與假設的數字相同的數，則數量加一，否則數量減一

如果數量減到0，則更換為0的數為當前的數字。

原理：

相同總數加一，不同總數減一，這么相互抵消下去，剩下的最終a，b所代表的數字一定是最多的

提交的代碼：

class?Solution?{

????public?List<Integer>?majorityElement(int[]?nums)?{

?????????List<Integer>?list?=?new?ArrayList<>();

?????????if(nums.length==0)

?????????{

????????????return?list;

?????????}

?????????int?a=nums[0],b=nums[0];

?????????int?count1=0,count2=0;

?????????for(int?i=0;i<nums.length;i++)

?????????{

????????????if(nums[i]==a)

????????????{

????????????????count1++;

????????????????continue;

????????????}

????????????else?if(nums[i]==b)

????????????{

????????????????count2++;

????????????????continue;

????????????}

????????????else{

????????????????if(count1==0)

????????????????{

????????????????????a?=?nums[i];

????????????????????count1=1;

????????????????????continue;

????????????????}

????????????????else?if(count2==0)

????????????????{

????????????????????b?=?nums[i];

????????????????????count2=1;

????????????????????continue;

????????????????}

????????????????else{

????????????????????count1--;

????????????????????count2--;

????????????????}

????????????}

?????????}

?????????count1=0;

?????????count2=0;

?????????for(int?i=0;i<nums.length;i++)

?????????{

????????????if(nums[i]==a)

????????????{

????????????????count1++;

????????????}

????????????else?if(nums[i]==b)

????????????{

????????????????count2++;

????????????}

?????????}

?????????if(count1>nums.length/3)

?????????{

????????????list.add(a);

?????????}

?????????if(a!=b&&count2>nums.length/3)

?????????{

????????????list.add(b);

?????????}

?????????return?list;

????}

}

總結

以上是生活随笔為你收集整理的Leetcode--229. 求众数Ⅱ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。