Happy New Year Everyone!
Today we'll be solving LeetCode question 347, in C#
Let's Dive in.
Problem Statement: 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]
Now, the way we will solve this is by using a dictionary and a PriortyQueue. If You don't know how to use a PriorityQueue you can review it here. The idea is to insert every element we have in the nums array as a Key in the dictionary, and the frequency of the items as the Value. Then, Initialize our PriorityQueue to take in elements in descending order, enqueue those items from the dictionary, and then dequeue them into our result array. We will take all these step by step with explanations at every operation.
The first thing we need to do is Initialize our Dictionary, PriorityQueue, and result Array
Dictionary<int,int> map = new ();
int[] result= new int[k];
PriorityQueue<int, int> queue = new PriorityQueue<int,int> (Comparer<int>.Create((a,b)=> b-a));
Remember, we are initializing our PriorityQueue to take in the frequency of Elements in descending order.
Next, We loop over our nums array and add the items as keys in our dictionary and the number of times they appear as the values
for(int i =0; i < nums.Length; i++){
if(!map.ContainsKey(nums[i])) map.Add(nums[i], 1);
else map[nums[i]]++;
}
Next, we are going to loop over our dictionary and Enqueue our PriorityQueue with the item key and item value(remember this is in descending order, so it will start with the highest frequency first)
foreach(var item in map){
queue.Enqueue(item.Key, item.Value);
}
After this, we want to dequeue(remove) the items from our queue into our result array, we are only looping over the queue until i < k
for(int i =0; i < k; i++){
result[i] = queue.Dequeue();
}
Then, we simply return the result.
return result;
And so, putting it all together, your solution should look something like this
public int[] TopKFrequent(int[] nums, int k) {
Dictionary<int,int> map = new ();
int[] result= new int[k];
PriorityQueue<int, int> queue = new PriorityQueue<int,int>(Comparer<int>.Create((a,b)=> b-a));
for(int i =0; i < nums.Length; i++){
if(!map.ContainsKey(nums[i])) map.Add(nums[i], 1);
else map[nums[i]]++;
}
foreach(var item in map){
queue.Enqueue(item.Key, item.Value);
}
for(int i =0; i < k; i++){
result[i] = queue.Dequeue();
}
return result;
}
Thanks for reading, I look forward to solving more Leetcode( and general Algorithmic) problems using C# in the future. Happing coding.
Top comments (0)