https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/799

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]

Example 2:

Input: nums = [1], k = 1
Output: [1] Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;


//good example for bucket sort
namespace SortingQuestions
{
    /// <summary>
    /// https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/799
    /// </summary>
    [TestClass]
    public class TopKFrequentTest
    {
        [TestMethod]
        public void SimpleUseCaseTest()
        {
            int[] nums = { 1, 1, 1, 2, 2, 3 };
            int k = 2;
            int[] expected = { 1, 2 };
            CollectionAssert.AreEqual(expected, TopKFrequentClass.TopKFrequent(nums, k).ToArray());
        }
    }

    public class TopKFrequentClass
    {
        public static IList<int> TopKFrequent(int[] nums, int k)
        {
            Dictionary<int, int> number2Count = new Dictionary<int, int>();

            //we count how many times each number appears
            foreach (var num in nums)
            {
                number2Count.TryGetValue(num, out var temp);
                number2Count[num] = temp + 1;
            }

            List<int>[] bucket = new List<int>[nums.Length + 1];

            //we allocate an array in the size of the original list of numbers
            //we iterate all of the numbers and for add each number to the index in the array
            // the index represents how many times that number appeared
            //
            //    0 times -> none
            //    1 times -> number 3
            //    2 times -> number 2
            //    3 times -> number 1
            //    4 times -> none
            //    5 times -> none
            foreach (var key in number2Count.Keys)
            {
                int frequency = number2Count[key];
                if (bucket[frequency] == null)
                {
                    bucket[frequency] = new List<int>();
                }
                bucket[frequency].Add(key);
            }

            List<int> result = new List<int>();
            // we iterate the list bucket in reverse until the number of items in the result
            // list equals k, because we iterate in reserve we get the biggest numbers
            for (int pos = bucket.Length - 1; pos >= 0 && result.Count < k; pos--)
            {
                if (bucket[pos] != null)
                {
                    result.AddRange(bucket[pos]);
                }
            }

            return result;
        }
    }
}

I really like this question and it me sometime to understand how to make the bucket sorting here.

I know I can also use MaxHeap. Since C# doesn't have a MaxHeap, do you think using a SortedList can help here somehow with the performance. remember the question limitations

Thanks please review for performance