//Solution1

class Solution {
     public List<Integer> majorityElement(int[] nums) {
        Arrays.sort(nums);
        int count = 1;
        List<Integer> result = new ArrayList<>();
        if (nums.length == 1){
            result.add(nums[0]);
            return result;
        }
        if(nums.length == 2){
            if(nums[0] == nums[1]){
                result.add(nums[0]);
            }else{
                result.add(nums[0]);
                result.add(nums[1]);
            }
            return result;
        }
        boolean flag = true;
        for(int i = 1;i < nums.length;i++){
            if(nums[i] == nums[i - 1]){
                count++;
            }else{
                flag = true;
                count = 1;
            }
            if(count > (nums.length / 3) && flag){
                result.add(nums[i - 1]);
                flag = false;
            }

        }
        return result;
    }
}

//Solution2
class Solution {
     public List<Integer> majorityElement(int[] nums){
        int x = 0;
        int y = 0;
        int cx = 0;
        int cy = 0;
        int count = 0;
        List<Integer> res = new ArrayList<>();
        for (int num : nums){
            if ((cx == 0 || num == x) && num != y){
                ++cx;
                x = num;
            } else if (cy == 0 || num == y){
                ++cy;
                y = num;
            } else {
                --cx;
                --cy;
            }
        }
        for (int num : nums){
            if (x == num){
                ++count;
            }
        }
        if (count > nums.length/3){
            res.add(x);
        }
        count = 0;
        for (int num : nums){
            if (y == num){
                ++count;
            }
        }
        if (count > nums.length/3 && x != y){
            res.add(y);
        }
        return res;
    }
}