Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Example 1:

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

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class MajorityElementII {
    public static void main(String[] args) {
        int[] nums = { 3, 2, 3 };
        List<Integer> elem = majorityElement(nums);
        System.out.println(Arrays.asList(elem));
    }

    static List<Integer> majorityElement(int[] nums) {
        HashMap<Integer, Integer> ump = new HashMap<Integer, Integer>();
        for (int i : nums)
            ump.put(i, ump.getOrDefault(i, 0) + 1);

        int cnt = nums.length / 3;
        List<Integer> res = new ArrayList<Integer>();
        for (int key : ump.keySet()) {
            if (ump.get(key) > cnt)
                res.add(key);
        }
        return res;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> majorityElement(vector<int> &nums)
{
    unordered_map<int, int> ump;
    for (int i = 0; i < nums.size(); i++)
        ump[nums[i]]++;
    int cnt = nums.size() / 3;
    vector<int> res;
    for (auto it = ump.begin(); it != ump.end(); it++)
    {
        if (it->second > cnt)
            res.push_back(it->first);
    }
    return res;
}

int main()
{
    vector<int> nums = {3, 2, 3};
    vector<int> elem = majorityElement(nums);
    cout << "[";
    for (int i = 0; i < elem.size() - 1; i++)
        cout << elem[i] << ",";
    cout << elem[elem.size() - 1] << "]";
    return 0;
}