Python Find Majority Number in O(n) time and O(1) memory [duplicate]

Question

I am working on my algorithm solving skills, and I am having trouble solving this problen in O(1) memory complexity.

Problem statement:

Given an array of integer numbers your task is to print to the standard output (stdout) the majority number. One number is considered majority if it occurs more than N / 2 times in an array of size N. Note: If no number is majority then print "None" Expected complexity: O(N) time, O(1) memory

Example input:

1 1 2 3 4 1 6 1 7 1 1

Example output:

1

Example input:

1 2 2 3

Example output:

None

Here is my code. I believe this is O(n) time (please correct me if I'm wrong), but this does not seem like O(1) memory. How can I achieve O(n) time and O(1) memory?

def majority(v):
    nums={}
    for num in v:
        if num in nums:
            nums[num]+=1
        else: nums[num]=1
    maxcount=['None',0]
    for num in nums:
        if nums[num] > maxcount[1] and nums[num] > len(v)/2: 
            maxcount[0] = num
            maxcount[1]=nums[num]
    print maxcount[0]

Answer 1

Here's Python implementation of the linear time constant space majority vote algorithm:

def majority_element(seq, default=None):
    """Find which element in *seq* sequence is in the majority.

    Return *default* if no such element exists.

    Use Moore's linear time constant space majority vote algorithm
    """
    candidate = default
    count = 0
    for e in seq:
        if count != 0:
            count += 1 if candidate == e else -1
        else: # count == 0
            candidate = e
            count = 1

    # check the majority
    return candidate if seq.count(candidate) > len(seq) // 2 else default

Example

print(majority_element("A A A C C B B C C C B C C".split()))
print(majority_element("A A A A C B C C C B C C".split()))

Output

C
None

There is no majority in the second case.