Easy to understand java solution


  • 0
    C
    public class Solution {
        public List<Integer> majorityElement(int[] nums) {
            List<Integer> res = new LinkedList<>();
            if(nums.length==0)return res;
            //get candidates
            int element1=0, element2=0;
            boolean e=false; //used for edge case where all the numbers in the array are the same number.
            int count1=0, count2=0;
            for(int i=0; i<nums.length; i++){
                if(count1==0){
                    element1=nums[i];
                    count1++;
                }
                else if(nums[i]==element1)count1++;
                else if(count2==0){
                    e=true;
                    element2=nums[i];
                    count2++;
                }
                else if(nums[i]==element2)count2++;
                else{
                    count1--;
                    count2--;
                }
            }
            //count votes
            count1=0; count2=0;
            for(int i=0; i<nums.length; i++){
                if(nums[i]==element1)count1++;
                else if(e&&nums[i]==element2)count2++;
            }
            //check if candidates have majority vote
            if(count1>nums.length/3)res.add(element1);
            if(e&&count2>nums.length/3)res.add(element2);
            return res;
        }
    }

  • 0
    W

    Nice solution using extension of Boyer-Moore algorithm (https://en.wikipedia.org/wiki/Boyer-Moore_Majority_Vote_Algorithm). However, I don't think there is a need of extra boolean variable e. The edge case mentioned will be handled without it as well.

    Below is a generalized version of this problem. Instead of n/3, it works for n/k for a given k >= 2. So, given an array and k, it gives list of integers who occur more than n/k times in the array.

    List<Integer> generalizedBoyerMoore(int[] nums, int k) {
    		Integer [] candidate = new Integer[k-1];
    		int[] count = new int[k-1];
    		int freq = nums.length / k;
    		for(int vote : nums) {
    			int i;
    			for(i = 0; i < count.length; i++) {
    				if(count[i] == 0 || vote == candidate[i]) {
    					count[i]++;
    					candidate[i] = vote;
    					break;
    				}
    			}
    			if(i == count.length) {
    				for(int j = 0; j < count.length; j++)
    					count[j]--;
    			}
    		}
    		
    		List<Integer> possible = new ArrayList<Integer>();
    		for(int i = 0; i < candidate.length; i++) {
    			if(candidate[i] != null)
    				possible.add(candidate[i]);
    			else break;
    		}
    		count = new int[possible.size()];
    		
    		for(int vote : nums) {
    			for(int i = 0; i < possible.size(); i++) {
    				if(vote == possible.get(i)) {
    					count[i]++;
    					break;
    				}
    			}
    		}
    		
    		List<Integer> result = new ArrayList<Integer>();
    		
    		for(int i = 0; i < count.length; i++)
    			if(count[i] > freq)
    				result.add(possible.get(i));
    		return result;
    }

Log in to reply
 

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