C# solution: Dictionary, linq to sort, add k items to list


  • 0
    H
    public class Solution {
        public IList<int> TopKFrequent(int[] nums, int k) {
            Dictionary<int, int> topNums = new Dictionary<int, int>();
                for(int i=0; i<nums.Length;i++)
                {
                    if (topNums.ContainsKey(nums[i]))
                        topNums[nums[i]]++;
                    else
                        topNums[nums[i]] = 1;
                }
    
                var dictItems = from pair in topNums orderby pair.Value descending select pair;
    
                int count = 0;
                IList<int> topKitems = new List<int>();
                foreach(var pair in dictItems)
                {
                    topKitems.Add(pair.Key);
                    count++;
                    if (count == k)
                        break;
                }
                return topKitems;
        }
    }
    

    I think this would be O(n log k). I know LINQ OrderBy methods use a stable quicksort, so they're O(N log N) average case. If I am wrong on the time complexity please let me know. I am unsure in cases like this problem.


  • 0
    Y

    you can get top k directly from linq:
    return (from pair in topNums
    orderby pair.Value desending
    select pari.Key).Take(k).ToList();


Log in to reply
 

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