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<Integer> 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. // step 1. find out those 2 majority elements
  8. // using Moore majority voting algorithm
  9. for (int i = 0; i < n; i++) {
  10. if (m1 != null && a[i] == m1) {
  11. c1++;
  12. } else if (m2 != null && a[i] == m2) {
  13. c2++;
  14. } else if (c1 == 0) {
  15. m1 = a[i]; c1 = 1;
  16. } else if (c2 == 0) {
  17. m2 = a[i]; c2 = 1;
  18. } else {
  19. c1--; c2--;
  20. }
  21. }
  22. // step 2. double check
  23. c1 = 0; c2 = 0;
  24. for (int i = 0; i < n; i++) {
  25. if (m1 != null && a[i] == m1) c1++;
  26. if (m2 != null && a[i] == m2) c2++;
  27. }
  28. List<Integer> res = new ArrayList<Integer>();
  29. if (c1 > n / 3) res.add(m1);
  30. if (c2 > n / 3) res.add(m2);
  31. return res;
  32. }
  33. }