0169 - Majority Element

0169 - Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Examples

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

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

Constraints

• n == nums.length

• 1 <= n <= 5 * 104

• -231 <= nums[i] <= 231 - 1

Java Solution

Sort (linear time and constant space)

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

Hashmap

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> hm = new HashMap<>();
        
        for(int i : nums) {
            if(hm.containsKey(i)) hm.put(i, hm.get(i) + 1);
            else hm.put(i, 1);
        }
        
        Map.Entry<Integer, Integer> majority = null;
        for(Map.Entry<Integer, Integer> entry : hm.entrySet()) {
            if(majority == null || entry.getValue() > majority.getValue()) majority = entry;
        }
        return majority.getKey();
    }
}