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

版权声明: 本文为博主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.


思路:

使用字典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.

上一篇:Android动画之Tween动画实战


下一篇:1.谈谈对Java平台的理解