Java O(n) solution


  • 4
    H
    public List<Integer> majorityElement(int[] nums) {
            int max1 = 0;
            int max2 = 1; //make sure these two numbers are different. 
            int count1 = 0;
            int count2 = 0;
            
            for (int num:nums) {
                if (num == max1) {
                    count1++;
                }
                else if (num == max2) {
                    count2++;
                }
                else if (count1 == 0) {
                    max1 = num;
                    count1 = 1;
                }
                else if (count2 == 0) {
                    max2 = num;
                    count2 = 1;
                }
                else {
                    count1--;
                    count2--;
                }
            }
            count1 = 0;
            count2 = 0;
            List<Integer> result = new ArrayList<Integer>();
            for (int num: nums){
                if (num == max1) {
                    count1++;
                }
                else if (num == max2) {
                    count2++;
                }
            }
            if (count1 > nums.length/3) {
                result.add(max1);
            }
            if (count2 > nums.length/3) {
                result.add(max2);
            }
            return result;
        }
    

  • 0
    M

    @haili2 why about the method to calculate the two bigest numbers


  • 0
    H

    @massic Since the question is to find all elements that appear more than ⌊ n/3 ⌋ times, we know there would be at most 2 elements. We first get the two biggest numbers and then judge if any of them satisfies the condition.


Log in to reply
 

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