Python 在 O(n) 时间和 O(1) 内存中查找多数数 [重复]

我正在研究我的算法解决技能，但我在解决 O(1) 内存复杂度的问题时遇到了困难。

问题陈述：

给定一个整数数组，您的任务是将多数数打印到标准输出 (stdout)。 如果一个数字在大小为 N 的数组中出现超过 N / 2 次，则该数字被视为多数。 注意：如果没有数字占多数，则打印“None” 预期复杂度：O(N) 时间，O(1) 内存

输入示例：

1 1 2 3 4 1 6 1 7 1 1

输出示例：

1

输入示例：

1 2 2 3

输出示例：

None

这是我的代码。我相信这是 O(n) 时间（如果我错了，请纠正我），但这看起来不像 O(1) 内存。如何实现 O(n) 时间和 O(1) 内存？

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]

这是Python的实现线性时间常数空间多数投票算法 http://www.cs.utexas.edu/~moore/best-ideas/mjrty/:

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

第二种情况没有多数。