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

  • 0
    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]] = 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)
                    if (count == k)
                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

    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.