In this Leetcode Majority Element problem solution we have 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.

Leetcode Majority Element problem solution


Problem solution in Python.

class Solution(object):
    def majorityElement(self, nums):
        candi, count = 0, 0
        for num in nums:
            if count == 0:
                candi = num
                count += 1
            elif num == candi:
                count += 1
            else:
                count -= 1
        return candi



Problem solution in Java.

public int majorityElement1(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num: nums) {
        if (map.containsKey(num))
            map.put(num, map.get(num) + 1);
        else
            map.put(num, 1);
        if (map.containsKey(num) && map.get(num) > nums.length/2)
            return num;
    }
    return -1;
}

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

public int majorityElement(int[] nums) {
    int majority = 0;
    int count = 0;
    for (int num: nums) {
        if (count == 0)
            majority = num;
        if (num == majority)
            count ++;
        else 
            count--;
    }
    return majority;
}


Problem solution in C++.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> myMap;
        int n = nums.size();
        int index = 0, i;
        unordered_map<int, int>::const_iterator got;
        for(i=0; i<n; i++)
        {
            got = myMap.find(nums[i]);
            if(got == myMap.end())
            {
                myMap.insert({nums[i], index});
                index++;
            }
        }
        
        vector<int> count(index, 0);
        for(i=0; i<n; i++)
            count[myMap[nums[i]]]++;
            
        int max = 0, maxIndex=0;
        for(i=0; i<index; i++)
            if(count[i]>max)
            {
                max = count[i];
                maxIndex = i;
            }
            
        for(i=0; i<n; i++)
            if(myMap[nums[i]] == maxIndex)
                return nums[i];
    }
};


Problem solution in C.

int majorityElement(int* nums, int numsSize){
    
    int major=0,c=1,i;
    int n=numsSize;
    for(i=1;i<n;i++)
    {
       if (nums[major]==nums[i]){
            c++;
          }
        else
            c--;
        if (c==0)
        {
            major=i;
            c=1;
        }
    }
    return nums[major];
}