Python在O(n)时间和O(1)内存中查找多数编号

Question

我正在研究我的算法求解技巧,而我在O(1)内存复杂性方面遇到了解决这个问题的麻烦.

问题陈述:

给定一个整数数组,您的任务是打印到标准输出(stdout)的多数.如果一个数字在大小为N的数组中出现超过N/2次,则认为是一个数字.注意:如果没有数字是多数,则打印"无"预期的复杂性: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]

Answer 1

这里是线性时间常数空间多数投票算法的Python实现:

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

例

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()))

产量

C
None

第二种情况没有多数.