如何在C#数组中找到众数？

Question

我想在数组中找到众数。我知道我需要做嵌套循环来检查每个值并查看数组中元素出现的频率。然后我必须计算第二个元素出现的次数。下面的代码不起作用，有人能帮我吗？

for (int i = 0; i < x.length; i ++)
{
    x[i]++;
    int high = 0;
    for (int i = 0; i < x.length; i++)
    {
        if (x[i] > high)
        high = x[i];
    }
}

- sarah

Answer 1

使用嵌套循环不是解决这个问题的好方法。它的运行时间为O(n^2)，比最优的O(n)要差得多。

您可以通过使用LINQ将相同的值分组，然后找到具有最大计数的组来完成此操作：

int mode = x.GroupBy(v => v)
            .OrderByDescending(g => g.Count())
            .First()
            .Key;

这既简单又快速。但请注意（与LINQ to SQL不同），当仅需要第一个结果时，LINQ to Objects目前不会优化OrderByDescending。它完全对整个结果集进行排序，这是O(n log n)操作。

您可能更喜欢这个O(n)算法。它首先通过组迭代一次来找到最大计数，然后再迭代一次以找到该计数的第一个相应键：

var groups = x.GroupBy(v => v);
int maxCount = groups.Max(g => g.Count());
int mode = groups.First(g => g.Count() == maxCount).Key;

你还可以使用 MoreLINQ 方法中的 MaxBy 扩展来进一步改进解决方案，以便仅需要遍历所有元素一次。

- Mark Byers

---

这绝对是最易读的方法，尽管它假设数组只有一个模式值（或者如果有多个值，则只需要其中一个）。 - LukeH

为什么你想让初学者一开始就学习LINQ呢？让她先理解数组等基础知识，然后再使用LINQ会更好。 - Pankaj Upadhyay

有两种类型的程序员。有一些人认为最好先学习低层次语言如C或汇编语言，以了解计算机的详细工作原理，然后再学习高级语言。还有一些人认为最好开始学习如何使用高级语言并让基本程序运行，然后再学习细节。我认为其中一组人特别喜欢大声地发表他们的意见，但我不认为任何一种方法是绝对正确或错误的。在我看来，这两种方法都是合理的学习方式。 - Mark Byers

@PankajUpadhyay：OP想要使用嵌套循环，但这是一个O(n^2)的解决方案，我认为这不是解决这个问题的合适方法。这就是为什么我展示了一种替代方案。如果你想发布一个嵌套循环的解决方案，请随意。OP获得的解决方案越多，她能够使用的可能性就越大。 - Mark Byers

我会在有时间的时候检查这个问题（如果我记得的话），但是在你的O(n)算法中，Count()调用不会遍历IGrouping来查找计数吗？所以实际上你的最坏情况是O(n^2)？ - Adam Goodwin

Answer 2

一种非LINQ的解决方案：

int[] x = new int[] { 1, 2, 1, 2, 4, 3, 2 };

Dictionary<int, int> counts = new Dictionary<int, int>();
foreach( int a in x ) {
    if ( counts.ContainsKey(a) )
        counts[a] = counts[a]+1
    else
        counts[a] = 1
}

int result = int.MinValue;
int max = int.MinValue;
foreach (int key in counts.Keys) {
    if (counts[key] > max) {
        max = counts[key];
        result = key;
    }
}

Console.WriteLine("The mode is: " + result);

- Petar Ivanov

---

result = key; 应该放在 if 语句的主体内吗？ - Mark Byers

为什么不直接用 counts[a]++; 呢？ - Necronomicron

Answer 3

作为一个初学者，这可能不太容易理解，但提供基于LINQ的解决方案是值得的。

x
.GroupBy(i => i) //place all identical values into groups
.OrderByDescending(g => g.Count()) //order groups by the size of the group desc
.Select(g => g.Key) //key of the group is representative of items in the group
.First() //first in the list is the most frequent (modal) value

- spender

---

LINQ版本在我看来比命令式等价物更有意义。 - LukeH

是的，我认为使用LINQ编写正确的代码更容易...但是除非熟悉LINQ，否则对于初学者程序员来说可能会感到困惑。 - spender

Answer 4

假设，x数组的项如下：

int[] x = { 1, 2, 6, 2, 3, 8, 2, 2, 3, 4, 5, 6, 4, 4, 4, 5, 39, 4, 5 };

a. 获取最高值：

int high = x.OrderByDescending(n => n).First();

b. 获取模态框：

int mode = x.GroupBy(i => i)  //Grouping same items
            .OrderByDescending(g => g.Count()) //now getting frequency of a value
            .Select(g => g.Key) //selecting key of the group
            .FirstOrDefault();   //Finally, taking the most frequent value

- Elias Hossain

---

一个小问题，如果没有值，使用 FirstOrDefault 会错误地声明数组的模式为 0。 - user7116