Mdthbs

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 took me some time to understand how to implement the bucket sorting.

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)

I am mainly looking for performance optimizations.

I think that in terms of performance you'd be hard pressed to do better than a LINQ query. Not only fast but very compact and relatively easy to understand. It could look something like this:

public IList<int> TopKFrequent(int[] nums, int k) {

    var answer = (from int n in nums

                  group n by n into g

                  orderby g.Count() descending 

                  select g.Key).Take((k)).ToList();

    return answer;

}