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

<分区>

我正在研究我的算法解决技巧，但我在解决这个 O(1) 内存复杂度的问题时遇到了麻烦。

问题陈述:

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

示例输入:

1 1 2 3 4 1 6 1 7 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]

最佳答案

这是 linear time constant space majority vote algorithm 的 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

第二种情况没有多数。

关于Python 在 O(n) 时间和 O(1) 内存中查找多数数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27652492/

上一篇：python - HTTP 服务器不工作(Python)

下一篇：qt - 从 QVariant 到整数和字符串

相关文章：

python - 使用全局变量有可能在导入过程中改变模块行为吗？

algorithm - 动态时间规整相似度百分比

c# - 遗传算法停止变异

python - 如何检查列表中的邻接关系，然后修复 python 中的邻接关系

python - 为什么handle_read方法没有被asyncore调用？

python - 为什么 del <object> 不删除它？

python - 递归调用合并排序算法

python - 涉及两个表的SQL语句

algorithm - 数组中上一个最近的更大的元素

python - 在 Python 3 中获取两个列表之间的交集