This code implements the problem of "Selecting M from N elements that appear more than M/N times". For more details, see http://wp.me/pL72j-5E

findmajority.py

import unittest

def FindMajority(array, M):
    '''Find elements that occurs more than(>) N/M times in the array of size N
    
    array: the array that is to be scanned through for elements returns a
    dictionary with keys set to elements that occur more than(>) N/M times in
    the array of size N. The key's values are their number of occurrences.

    '''
    counter = dict()
    for index, item in enumerate(array):
        # add to counter
        assert(len(counter) <= M)
        if item in counter:
            counter[item] += 1
        else:
            counter[item] = 1

        if index == len(array): break

        # cancel 1 occurrence if counter is full
        if len(counter) == M:
            for key in counter.keys():
                counter[key] -= 1
                if counter[key] == 0: del counter[key]

    assert(len(counter) <= M)
    # 2nd pass: count occurrences for items in counter.
    for item in counter:
        counter[item] = 0
    for item in array:
        if item in counter: counter[item] += 1

    # erase element if its number of occurrences <= M
    for key in counter.keys():
        if counter[key] <= len(array)/M: del counter[key] 

    return counter

class TestClass(unittest.TestCase):
    def test100(self):
        self.assertEqual(FindMajority("12321", 3), {"1":2, "2":2})

    def test110(self):
        self.assertEqual(FindMajority("12321", 2), {})

    def test150(self):
        # This doesn't select 1,2,3 because it has to be exactly MORE than 2
        self.assertEqual(FindMajority("112233", 3), {})

    def test160(self):
        self.assertEqual(FindMajority("112233", 4), {"1":2, "2":2, "3":2})

    def test200(self):
        self.assertEqual(FindMajority("11",2), {"1":2})

    def test300(self):
        self.assertEqual(FindMajority("432123447", 5), {"4":3, "3":2, "2":2})

    def test400(self):
        self.assertEqual(FindMajority("", 5), {})

if __name__ == "__main__":
    unittest.main()