c# - 使用 LINQ 选择数组中最小、最常见的数字

Question

如果我有一个未排序的数组，其中包含多对相同的数字，我如何找到最常见数字中的最小者？

int[] arr = new int[] {8, 6, 5, 2, 5, 9, 6, 9, 2, 3}; // unsorted array
// Array.Sort(arr); // I could sort the array

int mostCommon =  arr.GroupBy(ii => ii)  //Grouping same items
            .OrderByDescending(abc => abc.Count()) //now getting frequency of a value
            .Select(bcd => bcd.Key) //selecting key of the group
            .FirstOrDefault();   //Finally, taking the most frequent value

在上面的例子中，我想得到 2，但是查询返回 6。如果我在运行查询之前对数组进行排序，我将得到 2，但我想知道是否有一种方法可以使用 LINQ从未排序的数组中获取最小的最常见值。我对代码的快速执行不感兴趣。

Answer 1

有两个 2、两个 6 和两个 9 - 假设您的意思是在出现平局时应优先考虑最低的 (2)，那么您只需添加第二个排序，如下所示:

int mostCommon = arr.GroupBy(x => x)
            .OrderByDescending(grp => grp.Count()) // First precedence = frequency
            .ThenBy(grp => grp.Key) // Second precedence is lowest number first
            .Select(bcd => bcd.Key)
            .FirstOrDefault();

编辑，重新O(N)解决方案

这是一种方法，采用命令式方法，可以在一次数据传递中完成。鉴于您在数组中指定了单个数字，我假设 bin 计数数组的范围为 0-10(这样做的好处是这些值初始化为零)，但如果您的范围较大，则显然需要进行调整。如果您的值很大并且可能很稀疏，那么您可能需要用字典替换数组。

var bins = new int[10]; // Adjust this to size / use Dictionary if sparse
var hiCount = 0;
var smallestMostCommon = int.MaxValue;
foreach(var a in arr)
{
   var newCount = ++bins[a];
   if (newCount > hiCount) // 1st Precedence : Frequency
   {
      hiCount = newCount;
      smallestMostCommon = a;
   }
   else if (newCount == hiCount && a < smallestMostCommon) // 2nd : Lowest preferred
   {
      smallestMostCommon = a;
   }
}

我确信，进一步的优化是可能的，特别是在循环中的任何点，如果剩余元素的数量小于第一和第二最高容器之间的差值，则循环可以提前终止。