版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章,欲转载请先私信获博主允许,转载时请附上网址
http://blog.csdn.net/lzuacm。
C#版 - Leetcode 347. Top K Frequent Elements - 题解
在线提交: https://leetcode.com/problems/top-k-frequent-elements/
Description
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.
Difficulty:
Medium
Total Accepted: 109.7K
-
Total Submissions: 219.6K
Related Topics Hash TableHeap
Similar Questions Word FrequencyKth Largest Element in an ArraySort Characters By FrequencySplit Array into Consecutive SubsequencesTop K Frequent Words
思路:
使用字典Dictionary<int, int>存储每个数出现的次数,并对次数进行排序。有两种方法;
1.将Dictionary转为List,实现Sort的CompareTo方法;
2.使用Dictionary的OrderByDescending(f => f.value),并Take(k)。
由于转换为List后进行排序会让程序速度变慢,建议直接用后一种方法。
已AC代码:
public class Solution
{
public IList<int> TopKFrequent(int[] nums, int k)
{
var dict = new Dictionary<int, int>();
IList<int> result = new List<int>();
foreach (var num in nums)
{
if (!dict.ContainsKey(num))
dict.Add(num, 1);
else dict[num]++;
}
var list = dict.ToList();
list.Sort((x, y) => -x.Value.CompareTo(y.Value));
if (list.Count >= k)
{
for (int i = 0; i < k; i++)
{
result.Add(list.ElementAtOrDefault(i).Key);
}
}
return result;
}
}
改进版:
public class Solution
{
public IList<int> TopKFrequent(int[] nums, int k)
{
var dict = new Dictionary<int, int>();
IList<int> result = new List<int>();
foreach (var num in nums)
{
if (!dict.ContainsKey(num))
dict.Add(num, 1);
else dict[num]++;
}
var list = dict.OrderByDescending(f => f.Value).Take(k).ToList();
for (int i = 0; i < k; i++)
result.Add(list.ElementAtOrDefault(i).Key);
return result;
}
}
Rank:
You are here!
Your runtime beats 99.28 %
of csharp submissions.