In this Leetcode Majority Element II problem solution, you are given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Leetcode Majority Element II problem solution


Problem solution in Python.

import collections
class Solution:
    def majorityElement(self, nums):
        length = len(nums)
        counter = collections.Counter(nums)
        
        if length<3:
            return counter.keys()
        
        result = []
        
        words = counter.most_common(3)
        
        for i in range(0,min(3,len(counter))):
            if words[i][-1]>length/3:
                result.append(words[i][0])
        return result



Problem solution in Java.

public List<Integer> majorityElement(int[] nums) {
    List<Integer> result = new ArrayList<>();
    if(nums.length < 3){
        int n = nums.length;
        for(int i=0; i<n; i++){
            if(!result.contains(nums[i]))
                result.add(nums[i]);
        }
        return result;
    }
        
    Arrays.sort(nums);
    int count=1;
    int gt = nums.length/3;
    for(int i=0; i<nums.length-1; i++){
        if(nums[i] == nums[i+1]){
            count++;
        }
        if(count > 1 && nums[i] != nums[i+1]){ 
            count = 1;
        }
        if(count >= gt+1){
                if(!result.contains(nums[i])){
                    result.add(nums[i]);
                    count = 1;
                }
            }
    }
return result;
}


Problem solution in C++.

vector<int> majorityElement(vector<int>& nums) {
        vector<int> vec;
        int n= floor(nums.size()/3)+1;
        map<int,int> mp;
        map<int,int>::iterator it;    
        for(int i=0;i<nums.size();i++){
            it=mp.find(nums[i]);
            if(it==mp.end())        
                mp.insert(pair<int,int>(nums[i],1));        
            else it->second=mp[nums[i]]+1;        
        } 
        for(it=mp.begin();it!=mp.end();it++){
            if(it->second>=n)        
                vec.push_back(it->first);        
        }
        return vec;   
    }


Problem solution in C.

void add_back(int **ret, int *rS, int num){
    *ret = realloc(*ret, sizeof(int) * (*rS + 1));
    (*ret)[*rS] = num;
    *rS += 1;
    return;
}

int* majorityElement(int* nums, int numsSize, int* returnSize){
    *returnSize = 0;
    if(nums == NULL || numsSize < 1)
        return NULL;
    
   int cand1, cand2, count1, count2;
   cand1 = cand2 = count1 = count2 = 0;
   for (int i = 0; i < numsSize; i++) {
      int num = nums[i];
       if (cand1 == num) {
         count1++;   
       }else if (cand2 == num) {
         count2++;   
       }else if (count1 == 0) {
         cand1 = num;
         count1++;  
       }else if (count2 == 0) {
         cand2 = num;
         count2++;  
       }else {
         count1--;
         count2--;
      }
   }
   
   count1 = count2 = 0;
   for (int i = 0; i < numsSize; i++) {
      int num = nums[i];
      if (cand1 == num)
         count1++;
      else if (cand2 == num)
         count2++;
   }
   int *ret = NULL;

   if(count1 > numsSize/3)
      add_back(&ret, returnSize, cand1);
   
   if(count2 > numsSize/3)
      add_back(&ret, returnSize, cand2); 

   return ret;
}