Recently, it was necessary to do a task in which one of the subtasks was to find the most frequently occurring element in the array. If suddenly someone did not understand, an example:

Dan array: 3 4 5 3 6 7 5 3 3 3 3 8 5 4

Here the most common troika. Here it is necessary to withdraw

Click on the idea / algorithm with which you can implement it all?

ps solution was the following: create an array, the dimension of which is the maximum possible element in the array, then add to this array one by one when you meet an element from the first array. So go through the array, and then sort the second array by age and output the last element. But I think that this is a little perversion.

  • This is what olympiads such puzzles give? - DreamChild
  • Yandex. Algorithms - Hamsternik
  • what is this? Sedna was not like this - qulinxao
  • do you want to pervert? Long live associative arrays! ) - b2soft
  • Should work: arr.GroupBy (x => x) .OrderByDescending (g => g.Count) .First (). Key - VladD

2 answers 2

if nothing is known, then only sorting and then counting repetitions and selecting the most frequent.

if it is known that the most particular element is in more than half of the elements, that is, a simple algorithm (guess or google)

if, however, it is known in what range of elements, then it is possible by a counter.

in other cases, other specific features.

  • one
    Sort why? At best, you will sort by NlogN, and then linear time will be required to go through the array. And you can just walk through the array with the counting of elements in the hash table without any sorting and passing through the counters. - a_gura
  • 2
    a_gura makes a very typical mistake, forgetting about the time it takes to search the hash table. If for each element of the array to perform such a search, and in some cases also a modification of the hashtable, then the number of operations will be much more than NlogN. In this case, the speed of anything faster sorting is not done. Personally, in practice, repeatedly convinced of this. The task is generally typical. On large arrays, the difference in speed received an order of magnitude and higher. A solution with a hash table in some cases may be easier / more convenient for implementation, but sorting is faster. - reshu
  • one
    Hooray, for once, an algorithmic discussion! I will throw in: but, after all, insertion into hash table O (1), isn't it? - VladD

The easiest to understand algorithm: creating a second array b [0, 1, 2 ...] for each of the numbers and increment, for example, b [5] while finding a in [47] number 5.

Personally, I can advise you to read about the Boyer-Moore algorithm. This is a very simple, small and fast algorithm.

  • And if the numbers in the original array are 64-bit, what size are you going to get into the array b ? - VladD
  • This is like a very easy to understand algorithm. I'm not saying that you need to use it always and everywhere! In my opinion, it is suitable only for training. - SemperPeritus
  • @ Platon-Efimov: in general, this is a variant of the previous answer: sorting by count . - VladD
  • Yeah, okay, I realized that in general, even after creating an array, a string algorithm will be needed. Immediately the question in the subject line: which is better: KMP or BM ?? - hamsternik