Leetcode Majority Element problem solution

YASH PAL,

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];
}

coding problems solutions