Python Find the large number number in O (n) time and O (1) memory

Question

I am working on my skills in solving algorithms, and I am having problems solving this problem in O (1) memory complexity.

Description of the problem:

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

Input Example:

1 1 2 3 4 1 6 1 7 1 1 

Output Example:

 1 

Input Example:

 1 2 2 3 

Output Example:

 None 

Here is my code. I believe that this is O (n) time (please correct me if I am wrong), but it does not look 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 a Python implementation of linear time-space algorithm with lots of votes :

 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 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("AAACCBBCCCBCC".split())) print(majority_element("AAAACBCCCBCC".split())) 

Exit

 C None 

In the second case, there is no majority.