Python在O（n）时间和O（1）内存中查找多数数 [英] Python Find Majority Number in O(n) time and O(1) memory

问题描述

我正在研究自己的算法求解技能，但在解决O（1）内存复杂度方面的问题时遇到了麻烦。

I am working on my algorithm solving skills, and I am having trouble solving this problen in O(1) memory complexity.

问题陈述：

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

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

示例输入：

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）内存？

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?

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]

推荐答案

此处是线性时间常数空间多数投票算法：

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

在第二种情况下没有多数。

There is no majority in the second case.

这篇关于Python在O（n）时间和O（1）内存中查找多数数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！