229. Majority Element II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

Constraints:

• $1 <= nums.length <= 5 * 10^4$
• $-10^9 <= nums[i] <= 10^9$

Code

169. Majority Element

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int num1 = 0;
        int num2 = 0;
        int count1 = 0;
        int count2 = 0;

        for(int i = 0; i < nums.length; i++){
            if(nums[i] == num1){
                count1++;
            } else if (nums[i] == num2){
                count2++;
            } else if (count1 == 0){
                num1 = nums[i];
                count1 = 1;
            } else if (count2 == 0){
                num2 = nums[i];
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;
        for(int num : nums){
            if(num == num1){
                count1++;
            } else if(num == num2){
                count2++;
            }
        }

        List<Integer> res = new ArrayList<>();

        if(count1 > nums.length / 3){
            res.add(num1);
        }

        if(count2 > nums.length / 3){
            res.add(num2);
        }

        return res;
    }
}