The if statemens in Moore Voting alg. matters


  • 0
    L

    I was wondering why this code cannot pass the case:[1,2,2,3,2,1,1,3]

    public List<Integer> majorityElement(int[] nums) {
            List<Integer> ans = new ArrayList();
            int countA = 0, countB = 0, tmpA = 0, tmpB = 0;
            for(int num : nums){
                if(countA == 0 || tmpA == num){
                    tmpA = num;
                    countA+=1;
                }
                else if(countB == 0 || tmpB == num){
                    tmpB = num;
                    countB+=1;
                }
                else{
                    countA--;
                    countB--;
                }
            }
            countA = countB = 0;
            for(int num : nums){
                if(num == tmpA) countA++;
                if(num == tmpB) countB++;
            }
            System.out.println(countA+","+countB);
            System.out.println(tmpA+","+countA);
            if(countA>nums.length/3) ans.add(tmpA);
            if(countB>nums.length/3 && tmpA!=tmpB) ans.add(tmpB);
            return ans;
        }
    

    Can some explain the reason behind this to me? I know the general goal is to avoid tmpA==tmpB. But I need a clearer explanation...Thanks.


  • 0
    Y

    If you walk through the code with your test case, you will find the problem.
    In iteration 1 : countA==1, tmpA==1
    In iteration 2 : countB==2, tmpB==1
    In iteration 3 : countB==2, tmpB==2
    In iteration 4 : countA==1, tmpA==0 countB==2, tmpB==1
    In iteration 5 : countA==2, tmpA==1
    In iteration 6 : countA==2, tmpA==0 countB==2, tmpB==0
    In iteration 7 : countA==1, tmpA==1
    In iteration 8 : countA==1, tmpA==1 countB==3, tmpB==1

    You can see that after iteration 5, things go wrong(in fact it goes wrong at the first time, because your code logic is wrong :)

    The two majorities can not interfere each other. And in the iteration, tmpA can not equal tmpB. So when you want to change your candidate, you must make sure that the new candidate is not in your candidate set, which means you should first check n!=tmpA and n!=tmpB then you go to check if there is count==0 so you can change candidate.

    Therefor, corrected logic :
    if(tmpA == num)
    countA++;
    else if(tmpB == num){
    countB++;
    } else if(countA == 0){
    tmpA = num;
    countA = 1;
    } else if(countB == 0){
    tmpB = num;
    countB = 1;
    else{
    countA--;
    countB--;
    }


  • 0
    L

    Thanks! Learnt a lot!


Log in to reply
 

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