169 Majority Element

April 30, 2024

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Example 1: Input: [3,2,3] Output: 3

code

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int n: nums){
            m.put(n, m.getOrDefault(n, 0) + 1);
        }
        for (int k: m.keySet()){
            if (m.get(k) > nums.length/2) return k;
        }
        return 0;
    }
}

code

class Solution {
    public int majorityElement(int[] nums) {
        int c = 0, m = 0;
        for (int n: nums){
            if (c == 0) m = n;
            if (n == m) c++; // notice it's not else if here
            else c--;
        }
        return m;
    }
}

code

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

code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majorEle = nums[0]
        count = 1
        
        for i in range(1, len(nums)):
            if count == 0: majorEle = nums[i]
            if nums[i] == majorEle: count += 1
            else: count -= 1
            
        return majorEle

code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return collections.Counter(nums).most_common(1)[0][0]

code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

code

var majorityElement = function(nums) {
    let count = res = 0;
    for (let v of nums){
        if(count == 0) res = v;
        if (res == v) count++;
        else count--;
    }
    return res;
};