majority

majority.py

def majority(collection):
    if not collection:
        return None

    # initialize a candidate
    candidate = collection[0]
    chances = 1

    # go through the rest of the elements
    for c in collection[1:]:
        # increase the chances
        if c == candidate:
            chances += 1
        # change the candidate
        elif chances == 0:
            candidate = c
            chances = 1
        # decrease the chances
        else:
            chances -= 1
    # no viable candidate
    if chances == 0:
        return None

    # check again
    count = collection.count(candidate)

    # do we have a majority?
    if count > len(collection)/2:
        return candidate

    # nope, we don't
    return None