C#如何使递归函数返回整数数组中第n个最常见的整数

Question

C# 如何使递归函数返回整数数组中第 n 个最常见的整数

我正在使用 C#，我正在寻找最有效的内存方式来对整数列表按它们在整数数组中出现的频率进行排序，然后返回第 n 个数组元素，其中 nth 是一个整数，表示的降序键选择(最常用的整数、第二大最常用的整数、第三大最常用的整数等。

我可以使用 linq 和类似这样的东西来做到这一点......

public static void Main(string[] args)
{
    int x = NthMostCommon(new int[] { 5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5 }, 2);
    Console.WriteLine(x);
}

private static int NthMostCommon(int[] a, int k)
{
    int result = 0;
    var query = a.GroupBy(item => item).OrderByDescending(g => g.Count());
    if (query.Count() >= k)
    {
        result = query.ElementAt(k - 1).Key;
    }
    return result;
} 

这行得通，但有人告诉我，在处理较大的整数数组时，这不是获得所需结果的内存效率最高的方法。我看不出如何减少内存占用。无论大小如何，我都必须迭代整个数组。是的？

有什么想法吗？

提前致谢。

Answer 1

本文可能对您有所帮助。

http://www.developerfusion.com/article/84468/linq-to-log-files/

最常见的整数可能超过 1 个整数(请参阅我的代码中的 int 数组)，因此我使函数返回 int[] 而不仅仅是 int。

我还有 GroupBy，它在最坏的情况下(输入数组中的整数相同)可能与前一个一样有效。您也可以重写它。

    public static void Main(string[] args)
    {
        int[] x = NthMostCommon(new int[] { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6 }, 2);
        Console.WriteLine(x);
    }

    private static int[] NthMostCommon(int[] a, int k)
    {

        var query = GroupAndCount(a)
            .GroupBy(x => x.Value)
            .ToDictionary(x => x.Key, x => x.Select(n => n.Key))
            .OrderByDescending(x => x.Key);
        if (query.Count() >= k)
        {
            return query.ElementAt(k-1).Value.ToArray();
        }
        return null;
    }

    public static IEnumerable<KeyValuePair<T, int>> GroupAndCount<T>
    (IEnumerable<T> source)
    {
        Dictionary<T, int> dictionary =
            new Dictionary<T, int>();
        foreach (T element in source)
        {
            if (dictionary.ContainsKey(element))
            {
                dictionary[element]++;
            }
            else {
                dictionary[element] = 1;
            }
        }
        return dictionary;
    }