169. Majority Element

appear more than n / 2 times, then there must be only one such number, just find the number appeared most times, then it is the answer

class Solution {
    public int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int num = nums[0], count = 0;

        for (int i = 0; i < nums.length; i++){
            if (nums[i] == num){
                count++;
            }
            else if (count == 0){
                num = nums[i];
                count = 1;
            }
            else{
                count--;
            }
        }

        return num;
    }
}

229. Majority Element II

appear more than n / 3 times, then at most two such numbers, find the two numbers appeared most, answer could be one or two

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) return ans;

        int num1 = nums[0], num2 = nums[0], count1 = 0, 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 i = 0; i < nums.length; i++){
            if (nums[i] == num1) count1++;
            else if (nums[i] == num2) count2++;
        }

        if (count1 > nums.length / 3) ans.add(num1);
        if (count2 > nums.length / 3) ans.add(num2);

        return ans;
    }
}