从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;
}

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;
}