title: Python Find Majority Number in O(n) time and O(1) memory
body: <p>I am working on my algorithm solving skills, and I am having trouble solving this problen in O(1) memory complexity.</p>
  
  <p>Problem statement:</p>
  
  <p>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</p>
  
  <p><strong>Example input:</strong></p>
  
  <pre><code>1 1 2 3 4 1 6 1 7 1 1
  </code></pre>
  
  <p><strong>Example output:</strong></p>
  
  <pre><code>1
  </code></pre>
  
  <p><strong>Example input:</strong></p>
  
  <pre><code>1 2 2 3
  </code></pre>
  
  <p><strong>Example output:</strong></p>
  
  <pre><code>None
  </code></pre>
  
  <p>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?</p>
  
  <pre><code>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] &gt; maxcount[1] and nums[num] &gt; len(v)/2: 
              maxcount[0] = num
              maxcount[1]=nums[num]
      print maxcount[0]
  </code></pre>