Leetcode 347. Top K Frequent Elements
Shout out to NeetCode for this solution
# Intuition
Count number of occurences of each number, return the numbers with
the highest count.
# Approach
Bucket sort. Iterate through array counting occurences
and storing them in a dictionary.
Then add the values to a list of lists where
the index of the list is the count of the occurences of that value.
# Code
```
public class Solution
{
public int[] TopKFrequent(int[] nums, int k)
{
var counts = new Dictionary<int, int>();
var countsArr = new List<List<int>>();
for(int i = 0; i < nums.Length; i++)
{
//add new list to store numbers for each index
countsArr.Add(new List<int>());
//count occurences and add to dictionary
if(counts.ContainsKey(nums[i]))
{
counts[nums[i]]++;
}
else
{
counts.Add(nums[i], 1);
}
}
//loop through dictionary and add counts to corresponding
//index of countsArr
foreach(var val in counts)
{
//add the value - 1 to match zero based index of array
countsArr[val.Value -1].Add(val.Key);
}
//create array to hold result, make it length k
int[] result = new int[k];
//keep track of what index in the result we are currently setting
int curr = 0;
//loop through countsArr backwards to find biggest results first
for(int i = countsArr.Count - 1; i >= 0; i--)
{
//check if current index has any values
if(countsArr[i].Count > 0)
{
//loop through values at index, adding them to the result
for(int j = 0; j < countsArr[i].Count; j++)
{
//if curr == k we have added enough numbers
// to the result array, so return result
if(curr == k)
{
return result;
}
//otherwise set the current index of the result array
// to the current value
result[curr] = countsArr[i][j];
//increment current
curr++;
}
}
}
//return result to satisfy method signature
return result;
}
}