首页 > 代码库 > 347. Top K Frequent Elements
347. Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
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 Count Sort
public IList<int> TopKFrequent(int[] nums, int k) { var res = new List<int>(); if(nums.Count()==0) return res; var hashtable = new Dictionary<int,int>(); for(int i =0;i< nums.Count();i++) { if(hashtable.ContainsKey(nums[i])) hashtable[nums[i]]++; else hashtable.Add(nums[i],1); } //sort by count sort var dp = new List<int>(); foreach(var pair in hashtable) { dp.Add(pair.Value); } int a = FindK(dp,k); foreach(var pair in hashtable) { if(pair.Value >= a) res.Add(pair.Key); } return res; } public int FindK (List<int> nums, int k) { if(nums.Count()==0) return 0; int max = nums[0]; int min = nums[0]; var b = new int[nums.Count()]; foreach(int n in nums) { max = Math.Max(max,n); min = Math.Min(min,n); } int kk = max - min +1; var c = new int[kk]; for(int i =0;i<nums.Count() ;i++) { c[nums[i] - min] += 1; } for(int i =1;i<c.Count() ;i++) { c[i] = c[i] + c[i-1]; } for(int i = nums.Count()-1; i >= 0; i--){ b[--c[nums[i]-min]] = nums[i]; } return b[nums.Count() - k ]; }
347. Top K Frequent Elements
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。