229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

代碼如下：（方法一：超記憶體）

 1 public class Solution {
 2     public List<Integer> majorityElement(int[] nums) {
 3         List<Integer> list=new ArrayList<>();
 4         if(nums.length==0)
 5         return list;
 6         Arrays.sort(nums);
 7         int[] a=new int[nums[nums.length-1]+1];
 8         
 9         for(int i=0;i<nums.length;i++)
10             a[nums[i]]++;
11             
12         for(int i=0;i<nums.length;)
13         {
14             if(a[nums[i]]>nums.length/3)
15             {
16                 list.add(nums[i]);
17                 i=i+a[nums[i]]-1;
18             }
19         }
20       
21         
22         return list;
23     }
24 }

 方法二：（借鑒別人的）

 1 public class Solution {
 2     public List<Integer> majorityElement(int[] nums) {
 3         List<Integer> list=new ArrayList<>();
 4         if(nums.length==0)
 5         return list;
 6         if(nums.length==1)
 7         {
 8             list.add(nums[0]);
 9             return list;
10         }
11         int m1=nums[0];
12         int m2=0;
13         int c1=1;
14         int c2=0;
15         for(int i=1;i<nums.length;i++)
16         {
17             if(m1==nums[i])
18             c1++;
19             else if(m2==nums[i])
20             c2++;
21             else  if(c1==0)
22             {
23                 m1=nums[i];
24                 c1=1;
25             }
26             else if(c2==0)
27             {
28                m2=nums[i];c2=1; 
29             }
30             else {
31                 c1--;c2--;
32             }
33         }
34         c1 = 0; c2 = 0;  
35         for(int i=0; i<nums.length; i++) {  
36             if(m1 == nums[i]) ++c1;  
37             else if(m2 == nums[i]) ++c2;  
38         }  
39         if(c1>nums.length/3)
40         list.add(m1);
41         if(c2>nums.length/3)
42         list.add(m2);
43         
44         return list;
45     }
46 }