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.
Solution:
1. public class Solution {
2. public List majorityElement(int[] a) {
3. // we can only have maximum 2 majority elements
4. int n = a.length;
5. int c1 = 0, c2 = 0;
6. Integer m1 = null, m2 = null;
7. 8. // step 1. find out those 2 majority elements
9. // using Moore majority voting algorithm
10. for (int i = 0; i < n; i++) {
11. if (m1 != null && a[i] == m1) {
12. c1++;
13. } else if (m2 != null && a[i] == m2) {
14. c2++;
15. } else if (c1 == 0) {
16. m1 = a[i]; c1 = 1;
17. } else if (c2 == 0) {
18. m2 = a[i]; c2 = 1;
19. } else {
20. c1--; c2--;
21. }
22. }
23. 24. // step 2. double check
25. c1 = 0; c2 = 0;
26. 27. for (int i = 0; i < n; i++) {
28. if (m1 != null && a[i] == m1) c1++;
29. if (m2 != null && a[i] == m2) c2++;
30. }
31. 32. List res = new ArrayList();
33. 34. if (c1 > n / 3) res.add(m1);
35. if (c2 > n / 3) res.add(m2);
36. 37. return res;
38. }
39. }