在C#中获取给定整数数组中第k个常见元素

Question

我希望您能够找到一个数组中第k个最常见的元素，我已经成功找到了最常见的元素，但是我不知道如何找到第k个常见的元素。

我尝试过以下方法：

 private static int KthCommonElement(int[] a, int k)
 {   
     var counts = new Dictionary<int, int>();
     foreach (int number in a)
     {
         int count;
         counts.TryGetValue(number, out count);
         count++;
         //Automatically replaces the entry if it exists;
         //no need to use 'Contains'
         counts[number] = count;
     }
     int mostCommonNumber = 0, occurrences = 0;
     foreach (var pair in counts)
     {
         if (pair.Value > occurrences)
         {
             occurrences = pair.Value;
             mostCommonNumber = pair.Key;
         }
     }
     Console.WriteLine("The most common number is {0} and it appears {1} times", mostCommonNumber, occurrences);

    return mostCommonNumber;
}

- Dipak

---

这需要多高效？它需要比完全排序更高效吗？ - Matthew Watson

Answer 1

您可以按照它们的出现顺序对元素进行排序并取第k个元素：

int[] orderedByOccurence = a.OrderByDescending(i => counts[i]).ToArray();
if (orderedByOccurence.Length > k)
    Console.WriteLine($"{k}th most common element: {orderedByOccurence[k]});

但是正如Adam在评论中指出的那样，您可以使用“GroupBy”缩短代码：

private static int KthCommonElement(int[] a, int k)
{
    if (a == null) throw new ArgumentNullException(nameof(a));
    if (a.Length == 0) throw new ArgumentException();
    if (k < 0) throw new ArgumentOutOfRangeException();

    var ordered = a.GroupBy(i => i, (i, o) => new { Value = i, Occurences = o.Count()})
                     .OrderByDescending(g => g.Occurences)
                     .ToArray();

    int index = k;
    if (ordered.Length <= index)   
    {
        // there are less than k distinct values in the source array
        // so add error handling here, either throw an exception or
        // return a "magic value" that indicates an error or return the last element
        index = ordered.Length - 1;
    }

    var result = ordered[index];
    Console.WriteLine("The most common number is {0} and it appears {1} times", 
            result.Value, result.Occurrences);

    return result.Value;
}    

- René Vogt

---

如果你想用 GroupBy 来进行代码高尔夫比赛，也可以对计数本身进行人口统计。 - Adam Houldsworth

@ DipakAkhade，你能具体说明一下吗？是哪方面的改进？ - René Vogt

@DipakAkhade 我更新了答案，使其也输出了值的出现次数，就像你在问题中所做的那样。 - René Vogt

需要改进的代码：int index = k-1; - Dipak

@DipakAkhade 这取决于您将k作为参数传递的内容。数组是从零开始索引的。根据您简短的评论，我无法推断出k将会是什么样子。如果index = k-1;可以实现您想要的效果，那么请使用它。 - René Vogt