Algorithm
Problem Name: 347. Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104kis in the range[1, the number of unique elements in the array].- It is guaranteed that the answer is unique.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map < int, int>m;
for(auto x: nums) m[x]++;
priority_queue < pair<int, int>, vector<pair<int, int>>, greater < pair<int, int>>>pq;
for(auto p: m){
pq.push({p.second, p.first});
if(pq.size() > k) pq.pop();
}
vector<int>res;
while(k--) res.push_back(pq.top().second), pq.pop();
return res;
}
};
Input
nums = [1,1,1,2,2,3], k = 2
Output
[1,2]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
Map < Integer, List();
for (Integer key : map.keySet()) {
frequencyToValueMap.computeIfAbsent(map.get(key), j -> new ArrayList<>()).add(key);
}
List < Integer> result = new ArrayList<>();
for (int i = nums.length; i >= 0 && result.size() < k; i--) {
List values = frequencyToValueMap.getOrDefault(i, new ArrayList<>());
if (result.size() + values.size() < = k) {
result.addAll(values);
} else {
int idx = 0;
while (result.size() < k) {
result.add(values.get(idx++));
}
}
}
return result.stream().mapToInt(i -> i).toArray();
}
}
Input
nums = [1,1,1,2,2,3], k = 2
Output
[1,2]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const topKFrequent = function(nums, k) {
const hash = {}
for(let i = 0; i < nums.length; i++) {
if(hash.hasOwnProperty(nums[i])) hash[nums[i]]++
else hash[nums[i]] = 1
}
const res = new Array()
const keys = Object.keys(hash)
const bucket = new Array(nums.length)
for(let k of keys) {
let freq = hash[k]
if(bucket[freq] == null) {
bucket[freq] = []
}
bucket[freq].push(k)
}
for(let i = bucket.length - 1; i >= 0 && res.length < k; i--) {
if(bucket[i] != null) {
res.push(...bucket[i]>
}
}
return res
};
Input
nums = [1], k = 1
Output
[1]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
from collections import Counter as ct
return [k for (k,v) in ct(nums).most_common(k)]
Input
nums = [1], k = 1
Output
[1]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0347_TopKFrequentElements
{
public IList < int> TopKFrequent(int[] nums, int k)
{
var counts = new Dictionary<int, int>();
foreach (var num in nums)
{
if (!counts.ContainsKey(num))
counts.Add(num, 0);
counts[num]++;
}
return counts.OrderByDescending(pair => pair.Value).Select(pair => pair.Key).Take(k).ToList();
}
}
}
Input
nums = [1,1,1,2,2,3], k = 2
Output
[1,2]