2-1

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (entry.getValue() > nums.length / 2) {
                return entry.getKey();
            }
        }
        return Integer.MIN_VALUE;
    }
}



class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = -1;
        for (int num : nums) {
            // If count of the current candidate number became 0,
            // pick a new candidate number.
            if (count == 0) candidate = num;

            // If current number is the candidate number,
            // increase count by 1.
            if (num == candidate) count++;
            // Otherwise, decrement count by 1. You can think
            // of it like "a single non-candidate number kills a single candidate number".
            else count--;
        }
        // Since there is one number that appears > n/2 times, it is un-killable.
        // Hence, it should win over all other candidates.
        return candidate;
    }
}



class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return nums[n / 2];
    }
}