-1

So I am trying to figure an algorithm to search through an array with just a single pass to find the most frequent number occur in it. I have tried using two inner loops to solve it and it works but that requires going through the array in a loop of multiple times.

Right now, I am trying to figure another way of doing it by just "scanning" the array in one go to find the most frequent number. Anyone have any suggestion that will help?

ProgrammingLlama
  • 36,677
  • 7
  • 67
  • 86
TomCold
  • 83
  • 6
  • Possible duplicate of [The Most frequent Number in an array](https://stackoverflow.com/questions/279359/the-most-frequent-number-in-an-array). LINQ-specific duplicates: [Find the most occurring number in a List](https://stackoverflow.com/questions/355945/find-the-most-occurring-number-in-a-listint), [Find the most frequent numbers in an array using LINQ](https://stackoverflow.com/questions/1169299/find-the-most-frequent-numbers-in-an-array-using-linq) – Lance U. Matthews Sep 29 '18 at 21:00

3 Answers3

2

With LINQ you can simply use,

var mostfrequent = myList.GroupBy(i=>i).OrderByDescending(grp=>grp.Count())
      .Select(grp=>grp.Key).First();

DOTNET FIDDLE

EDIT

Based on OP's requirement using Hashtable , it can be implemented as follows,

            int mostCommom = array[0];
            int occurences = 0;
            foreach (int num in array)
            {
                if (!hs.ContainsKey(num))
                {
                    hs.Add(num, 1);
                }
                else
                {
                    int tempOccurences = (int)hs[num];
                    tempOccurences++;
                    hs.Remove(num);
                    hs.Add(num, tempOccurences);

                    if (occurences < tempOccurences)
                    {
                        occurences = tempOccurences;
                        mostCommom = num;
                    }
                }
            }
            foreach (DictionaryEntry entry in hs)
            {
                Console.WriteLine("{0}, {1}", entry.Key, entry.Value);
            }
            Console.WriteLine("The commmon numer is " + mostCommom + " And it appears " + occurences + " times");

most frequent element in an Array

Sajeetharan
  • 216,225
  • 63
  • 350
  • 396
0

You could use a Dictionnary and set the key to the number then when you meet a number you already met add 1 to the value of the current number (which is the key) and when the array is finished pick the key with the highest value.

nalka
  • 1,894
  • 11
  • 26
  • does that break the rule ? – TomCold Sep 29 '18 at 14:47
  • or is it more effiicient to use hashtable? – TomCold Sep 29 '18 at 14:48
  • No, you just need to loop through the array once – nalka Sep 29 '18 at 14:48
  • I think Sajeetharan's comment on the first answer is actualy what i just said but in code version ^^ – nalka Sep 29 '18 at 14:49
  • Yea but i am trying to know what's the diff using dictionary or hashtable – TomCold Sep 29 '18 at 14:51
  • A dictionary is a hash table. What "rule" does it break? You'd use a `Dictionary` and extra variables that kept track of the current maximum winner and its count. Do that, and you should be able to do it in _O(N)_, i.e., one pass. – Flydog57 Sep 29 '18 at 14:55
  • @Flydog57 Using hashtable would equally give me a one pass, O(N) complexity, am i right? – TomCold Sep 29 '18 at 14:58
  • Yes. Start with two variables, one representing the currently most frequent number and the other its count. Then loop through your list of ints. If the current value is not in the dictionary, add an entry, key=the current int, value=1. If it is in the dictionary, increment it's associated value. After that (still for each int), Update those two variables if you have a new max frequency value. – Flydog57 Sep 29 '18 at 15:33
0

Something like this should work (you need to get the ValueTuple NuGet package for that tuple call signature to work):

 public static IEnumerable<int> ListOfInts = new List<int> { 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5 };

 public static (int? mostFrequent, int numOccurances) FindMostFrequent(IEnumerable<int> ints) {
     int maxNumOccurances = int.MinValue;
     int? mostFrequent = null;
     //key is number (that occurs), value is number of occurances
     var counters = new Dictionary<int, int>();
     foreach (var num in ints) {
         if (counters.TryGetValue(num, out var occurances)) {
             counters[num] = ++occurances;
         } else {
             counters[num] = 1;
         }
         if (occurances > maxNumOccurances) {
             mostFrequent = num;
             maxNumOccurances = occurances;
         }
     }
     return (mostFrequent, maxNumOccurances);
 }

It goes through the integer collection once. It builds a Dictionary<int, int> as it walks through the list, doing N lookups and N writes (either inserts or replacements).

If the list is empty, the mostFrequent part of the return will be null. If there the maximum occurs more than once, you'll get the first one that's found. If you want the last, change the > to >= in:

if (occurances > maxNumOccurances)

and, if you want all possible results, do something like this before the return:

var maxes = from pair in counters where pair.Value == maxNumOccurances select pair;
Flydog57
  • 6,851
  • 2
  • 17
  • 18