Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

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

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class TopKFrequentElements {
    public static void main(String[] args) {
        int[] nums = { 1, 1, 1, 2, 2, 3 };
        int k = 2;
        int[] freq = topKFrequent(nums, k);
        System.out.println(Arrays.toString(freq));
    }

    private static int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        // sort the map using value
        map = map.entrySet().stream().sorted(Map.Entry.
            comparingByValue(Comparator.reverseOrder())).collect(
                Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
         (o1V, o2V) -> o1V, LinkedHashMap::new));
        List<Integer> l = new ArrayList<Integer>();
        for (Integer i : map.keySet()) {
            l.add(i);
            k--;
            if (k == 0) {
                break;
            }
        }
        return l.stream().mapToInt(Integer::intValue).toArray();
    }
}

C++

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

bool static cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    return (a.second > b.second);
}
vector<int> topKFrequent(vector<int> &nums, int k)
{
    sort(nums.begin(), nums.end());
    int i = 0;
    int n = nums.size();
    vector<int> res;
    vector<pair<int, int>> v;
    int cnt = 1;
    while (i < n - 1)
    {
        if (nums[i] == nums[i + 1])
        {
            cnt++;
            i++;
        }
        else
        {
            v.push_back({nums[i], cnt});
            cnt = 1;
            i++;
        }
    }
    v.push_back({nums[i], cnt});
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < k; i++)
        res.push_back(v[i].first);
    return res;
}

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