C# OA using Hash and bucket sort


  • 2
    Y
     public class Solution {
        public IList<int> TopKFrequent(int[] nums, int k) {
        
        //bucket sort 
        
        var frenquecyDict=new Dictionary<int,int>();
        
        int maxFrenquecy = 0;
        
        for(int i=0;i<nums.Length;i++)
        {
            if(frenquecyDict.ContainsKey(nums[i]))
            {
                frenquecyDict[nums[i]]+=1;
            }
            else
            {
                frenquecyDict.Add(nums[i],1);
            }
            
            if(frenquecyDict[nums[i]]>maxFrenquecy)
            {
                maxFrenquecy = frenquecyDict[nums[i]];
            }
        }
        
        var bucket = new List<int>[maxFrenquecy + 1];
        
        foreach(var item in frenquecyDict)
        {
            if (bucket[item.Value] == null) {
            bucket[item.Value] = new List<int>();
            }
            bucket[item.Value].Add(item.Key);
        }
        
        var result = new List<int>();
        
        for(int i=maxFrenquecy; i>0 && result.Count<k; i--)
        {
            if(bucket[i]!=null)
            {
                result.AddRange(bucket[i]);
            }
        }
        
        return result;
      }
    }

  • 0
    X

    Thank you so much friend. Your solution worked perfectly.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.