How to find smallest number in array, that is repeated the most. c# [duplicate]

If I have an unsorted array, which has multiple pairs of identical numbers, how can I find the smallest of the most common number?

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

In the above case, I want to get 2, but the query returns 6. If I sort the array before running the query, I will get 2, but I want to find out if there is a way to use LINQ to get the smallest most common value from an unsorted array. I am not interested in very fast execution of the code.

Solution 1:

There are two 2's, two 6's and two 9's - assuming that you mean the lowest (2) should have precedence in the event of a tie, then you simply need to add in a second ordering, like so:

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();

Edit, re O(N) solution

Here's one way, resorting to imperative means, which can be done in a single pass through the data. Given that you've specified single digits in your array, I've assumed a range of 0-10 for a bin counting array (with the benefit that the values are initialized to zero), but obviously adjust if your range is larger. If your values are large and likely to be sparse, then you may need substitute a Dictionary for the array.

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

Further optimizations are possible, I'm sure, notably that at any point in the loop, that if the number of elements remaining is less than the difference between the first and second highest bins, that the loop can terminate early.

Solution 2:

You need to order items again before Select, so FirstOrDefault would return the smallest group key:

int smallestMostCommon =  arr.GroupBy(ii => ii)  //Grouping same items
        .OrderByDescending(abc => abc.Count()) //now getting frequency of a value
        .ThenBy(g => g.Key) // Make sure we get the smallest key first
        .Select(bcd => bcd.Key) //selecting key of the group
        .FirstOrDefault();   //Finally, taking the most frequent value