Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find the most occurring number in a List<int>

Tags:

c#

list

linq

How about:

var most = list.GroupBy(i=>i).OrderByDescending(grp=>grp.Count())
      .Select(grp=>grp.Key).First();

or in query syntax:

var most = (from i in list
            group i by i into grp
            orderby grp.Count() descending
            select grp.Key).First();

Of course, if you will use this repeatedly, you could add an extension method:

public static T MostCommon<T>(this IEnumerable<T> list)
{
    return ... // previous code
}

Then you can use:

var most = list.MostCommon();

Not sure about the lambda expressions, but I would

  1. Sort the list [O(n log n)]

  2. Scan the list [O(n)] finding the longest run-length.

  3. Scan it again [O(n)] reporting each number having that run-length.

This is because there could be more than one most-occurring number.


Taken from my answer here:

public static IEnumerable<T> Mode<T>(this IEnumerable<T> input)
{            
    var dict = input.ToLookup(x => x);
    if (dict.Count == 0)
        return Enumerable.Empty<T>();
    var maxCount = dict.Max(x => x.Count());
    return dict.Where(x => x.Count() == maxCount).Select(x => x.Key);
}

var modes = { }.Mode().ToArray(); //returns { }
var modes = { 1, 2, 3 }.Mode().ToArray(); //returns { 1, 2, 3 }
var modes = { 1, 1, 2, 3 }.Mode().ToArray(); //returns { 1 }
var modes = { 1, 2, 3, 1, 2 }.Mode().ToArray(); //returns { 1, 2 }

I went for a performance test between the above approach and David B's TakeWhile.

source = { }, iterations = 1000000
mine - 300 ms, David's - 930 ms

source = { 1 }, iterations = 1000000
mine - 1070 ms, David's - 1560 ms

source = 100+ ints with 2 duplicates, iterations = 10000
mine - 300 ms, David's - 500 ms

source = 10000 random ints with about 100+ duplicates, iterations = 1000
mine - 1280 ms, David's - 1400 ms


Here is another answer, which seems to be fast. I think Nawfal's answer is generally faster but this might shade it on long sequences.

public static IEnumerable<T> Mode<T>(
    this IEnumerable<T> source,
    IEqualityComparer<T> comparer = null)
{
    var counts = source.GroupBy(t => t, comparer)
        .Select(g => new { g.Key, Count = g.Count() })
        .ToList();

    if (counts.Count == 0)
    {
        return Enumerable.Empty<T>();
    }

    var maxes = new List<int>(5);
    int maxCount = 1;

    for (var i = 0; i < counts.Count; i++)
    {
        if (counts[i].Count < maxCount)
        {
            continue;
        }

        if (counts[i].Count > maxCount)
        {
            maxes.Clear();
            maxCount = counts[i].Count;
        }

        maxes.Add(i);
    }

    return maxes.Select(i => counts[i].Key);
}