相关疑难解决方法(0)

如线性时间多数算法的答案所示？,可以在线性时间和log(n)空间中计算元素数组的大部分.

结果表明,每个看过这种算法的人都认为这是一种很酷的技巧.但这个想法是否会推广到新算法？

似乎这个算法的隐藏力量在于保持一个扮演复杂角色的计数器 - 例如"(到目前为止多数元素的数量) - (到目前为止第二多数的计数)".是否存在基于相同想法的其他算法？

如果存在这样的元素,则多数表决算法决定序列中的哪个元素占多数.这是我在试图理解它时发现的最常被引用的链接.

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

此外,我们在这里有一个讨论问题的链接:

如何找到重复至少N/2次的数组元素？

问题是标记为正确的答案是错误的.请注意,该问题实际上允许输入具有单个元素的正好 N/2个副本(不一定多于 N/2,如通常在多数元素检测算法中假设的那样).

我复制了代码并尝试使用[1,2,3,2]和[1,2,3,2,6,2]等输入(产生3和6的结果).这实际上也适用于上面引用的算法(返回"无多数元素!").问题在于:只要多数元素和其他任何元素之间存在交替,就会选择数组中不是多数元素的最后一个元素.请更正我的错误想法,并告诉我如何在实施中避免它.

我正在研究我的算法求解技巧,而我在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]