C#版(打败99.28%的提交) - Leetcode 347. Top K Frequent Elements - 题解

Enjoy233

发布于 2019-03-05 15:37:25

9410

发布于 2019-03-05 15:37:25

文章被收录于专栏：大白技术控的技术自留地

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 Table Heap Similar Questions Word Frequency Kth Largest Element in an Array Sort Characters By Frequency Split Array into Consecutive Subsequences Top 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.

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年06月10日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度