Boyer-Moore method Java Implementation.


  • 20
    C
    public class Solution{
    	public List<Integer> majorityElement(int[] nums){
    		List<Integer> rst = new ArrayList<Integer>();
    		if(nums == null || nums.length == 0) return rst;
    		int count1 = 0, count2 = 0, candidate1 = 0, candidate2 = 1;
    		for(int num : nums){
    			if(num == candidate1) count1++;
    			else if(num == candidate2) count2++;
    			else if(count1 == 0){
    				candidate1 = num;
    				count1 = 1;
    			}
    			else if(count2 == 0){
    				candidate2 = num;
    				count2 = 1;
    			}
    			else{
    				count1--;
    				count2--;
    			}
    		}
    		count1 = 0; count2 = 0;
    		for(int num : nums){
    			if(num == candidate1) count1+=2;
    			else count1--;
    			if(num == candidate2) count2 += 2;
    			else count2--;
    		}
    		if(count1 > 0) rst.add(candidate1);
    		if(count2 > 0) rst.add(candidate2);
    		return rst;
    	}
    }

  • -59
    W

    dsrwwe

    ew
    wr
    wq
    we

    wqrwq
    rwq
    r
    qr
    qw
    rwq

    q
    rq
    qew
    rewq
    rewqr
    w
    rewq
    we
    rwq


  • 0
    J

    Cool implementation, but this won't return multiple numbers much less numbers which pass a threshold of floor(N/3)


  • 0
    Q

    cool inspiration, thank you!


  • 0
    C

    Edited my answer to make it right, thank you


  • 0
    H

    !!!!!!!!do not work for [0,0,0]


  • 2
    P

    Almost identical code in C++. Moore algorithm. 2N time complexity.

    vector<int> majorityElement(vector<int>& nums) {
        int a, b, cnta(0), cntb(0);
        for(auto i:nums) {
            if(cnta && i == a) cnta++;
            else if(cntb && i == b) cntb++;
            else if(!cnta) {
                cnta = 1;
                a = i;
            }
            else if(!cntb) {
                cntb = 1;
                b = i;
            }
            else {
                cnta--;
                cntb--;
            }
        }
        if(!cnta && !cntb) return {};
        cnta = cntb = 0;
        for(auto i:nums) {
            if(i == a) cnta++;
            if(i == b) cntb++;
        }
        vector<int> ret;
        if(cnta > nums.size() / 3) ret.push_back(a);
        if(b!= a && cntb > nums.size() / 3) ret.push_back(b);
        return ret;
    }

  • 1

    this is an accurate representation of my frustration right now!


Log in to reply
 

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