01... "" Impl
01...
""
Implementation of the Misra-Gries algorithm.
Given a list of items and a value k, it returns the every item in the list
that appears at least n/k times, where n is the length of the array
By default, k is set to 2, solving the majority problem.
For the majority problem, this algorithm only guarantees that if there is
an element that appears more than n/2 times, it will be outputed. If there
is no such element, any arbitrary element is returned by the algorithm.
Therefore, we need to iterate through again at the end. But since we have filtred
out the suspects, the memory complexity is significantly lower than
it would be to create counter for every element in the list.
For example:
Input misras_gries([1,4,4,4,5,4,4])
Output {'4':5}
Input misras_gries([0,0,0,1,1,1,1])
Output {'1':4}
Input misras_gries([0,0,0,0,1,1,1,2,2],3)
Output {'0':4,'1':3}
Input misras_gries([0,0,0,1,1,1]
Output None
"""..

Step by step
Solved in 3 steps with 1 images
