AC clean Java solution


  • 0
    public List<Integer> majorityElement(int[] a) {
      // we can only have maximum 2 majority elements
      int n = a.length;
      int c1 = 0, c2 = 0;
      Integer m1 = null, m2 = null;
      
      // step 1. find out those 2 majority elements
      // using Moore majority voting algorithm
      for (int i = 0; i < n; i++) {
        if (m1 != null && a[i] == m1)      { c1++; } 
        else if (m2 != null && a[i] == m2) { c2++; }
        else if (c1 == 0)                  { m1 = a[i]; c1 = 1; }
        else if (c2 == 0)                  { m2 = a[i]; c2 = 1; } 
        else                               { c1--; c2--; }
      }
      
      // step 2. double check
      c1 = 0; c2 = 0;
      
      for (int i = 0; i < n; i++) {
        if (m1 != null && a[i] == m1) c1++;
        if (m2 != null && a[i] == m2) c2++;
      }
      
      List<Integer> res = new ArrayList<Integer>();
      
      if (c1 > n / 3) res.add(m1);
      if (c2 > n / 3) res.add(m2);
      
      return res;
    }

  • 0
    F

    This will fail input = { 0, -1, 2, -1 };


  • 0

    My code gives the result as {-1} which should be the correct answer. Otherwise, please tell me what the expected result should be.


  • 0
    F

    My bad. You are right.


  • 0
    M

    I don't understand why there is a need to do double-check?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.