implementation of the misragries algorithm given a list of items and a value k it returns the every item in the list that appears at least nk 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 n2 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 misrasgries1 4 4 4 5 4 4 output 4 5 input misrasgries0 0 0 1 1 1 1 output 1 4 input misrasgries0 0 0 0 1 1 1 2 2 3 output 0 4 1 3 input misrasgries0 0 0 1 1 1 output none misragries algorithm keyword arguments array list of integers k value of k default 2 misra gries algorithm keyword arguments array list of integers k value of k default 2
def misras_gries(array,k=2):
    
    keys = {}
    for i in array:
        val = str(i)
        if val in keys:
            keys[val] = keys[val] + 1

        elif len(keys) < k - 1:
            keys[val] = 1

        else:
            for key in list(keys):
                keys[key] = keys[key] - 1
                if keys[key] == 0:
                    del keys[key]

    suspects =  keys.keys()
    frequencies = {}
    for suspect in suspects:
        freq = _count_frequency(array,int(suspect))
        if freq >= len(array) / k:
            frequencies[suspect] = freq

    return frequencies if len(frequencies) > 0 else None


def _count_frequency(array,element):
    return array.count(element)