Java AC solution linear time constant space


  • 0
    I

    The logic involves extending the Boyer Moore voting algo to 2 candidates:

    public class Solution {
    public List<Integer> majorityElement(int[] nums) {
    List<Integer> list = new ArrayList<Integer>();
    int candidate1 = 0;
    int candidate2 = 0;
    int count1 = 0;
    int count2 = 0;
    int i = 0;

        for (i = 0; i < nums.length; i++) {
            if (count1 == 0) {
                candidate1 = nums[i];
            }
            else if (count2 == 0 && nums[i] != candidate1) {
                candidate2 = nums[i];
            }
            if (nums[i] == candidate1) {
                count1++;
            }
            else if (nums[i] == candidate2) {
                count2++;
            }
            else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] == candidate1) {
                count1++;
            }
            if (nums[i] == candidate2) {
                count2++;
            }
        }
        if (count1 > nums.length/3) {
            list.add(candidate1);
        }
        if (count2 > nums.length/3 && candidate2 != candidate1) {
            list.add(candidate2);
        }
        return list;
    }
    

    }


Log in to reply
 

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