My java solution using two candidates


  • 0
    M

    public List<Integer> majorityElement(int[] nums) {
    // two mark num do the similiar as majority element I
    // the first step to find the possible two number which its occurances more than n/3
    // seconde step to calcu the occurance times of both num
    // convert Integer to int use intValue
    List<Integer> result = new ArrayList<Integer>();
    Integer candidate1 = null;
    Integer candidate2 = null;
    int count1 = 0;
    int count2 = 0;
    for(int num : nums) {
    if(candidate1 != null && candidate1.intValue() == num) {
    count1++;
    } else if(candidate2 != null && candidate2.intValue() == num) {
    count2++;
    } else if(count1 == 0) {
    count1 = 1;
    candidate1 = num;
    } else if(count2 == 0) {
    count2 = 1;
    candidate2 = num;
    } else {
    count1--;
    count2--;
    }
    }
    // after we get the two possible value and we need one more loop to calculate these two value occurence times
    count1 = count2 = 0;
    for(int num : nums) {
    if(num == candidate1.intValue()) count1++;
    else if(num == candidate2.intValue()) count2++;
    }
    // add the suitable result
    if(count1 > nums.length / 3) result.add(candidate1);
    if(count2 > nums.length / 3) result.add(candidate2);
    return result;
    }


Log in to reply
 

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