摩尔计数法

如何在任意多的候选人中（选票无序），选出获得票数最多的那个

算法描述

想象这样一个场景，有N个人投票选举，得票数超过一半的可以担任某职位，那么如何快速确定投票结果呢？

我们从结果倒推，假设A得票数超过了一半，也就是说，没有选择A的票数小于一半，这样我们就有了一个关于票数量的大小比较，N>A的票数>N/2>不选A的票数>=0，所以A的票数-不选A的票数>0这个一定是成立的。

这就是摩尔投票法的主要思路，让我们用打擂台的方式形象化的描述一下。我们有A,B,C三位候选人，支持不同候选人的投票者会成为对应的拳击手，每位拳击手可以击倒一名其他阵营的拳击手，同时自己也被击倒。那么所有不同阵营的拳击手互相打擂台，最后剩下的拳击手，一定是属于得票数最多(>N/2)的阵营。

注意，这里隐含了一个限制条件，即一定存在得票数超过一半的A。因此，为了保证所得结果的合法性，需要重新统计一下A的得票数，是否超过了一半。

以上就是摩尔投票法的主要思路，算法设计据此实现。

时间复杂度： O(n)

空间复杂度： O(n)

实现步骤

过程梳理

算法分为两个阶段：

pairing阶段：两个不同阵营的拳击手对抗，同时击倒对方，直到剩下的人都属于同一阵营。
counting阶段：统计最后阵营的得票总数

伪代码

初始化元素m和计数器i=0
对于输入序列中的每一个元素x：
如果i=0，将x赋值给元素m，同时令 i=1
如果x的值与m的值相同，则令 i = i + 1
否则，i = i -1
返回元素m

具体实现

class Solution(object):
  def majorityNumber(self, nums: List[str]):
      """
      @params:
        nums: 投票列表
      @return:
        str/None: 当前多数元素/不存在多数元素
      """
      result = ""  # 主要元素
      count = 0  # 计数器

      # 阶段一：不同阵营票数抵消
      for num in nums:
          # 计数器为0时，初始化主要元素及计数器
          if count == 0:
              result = num
              count += 1  # or count = 1
          # 当前元素等于主要元素时，计数器+1
          elif num == result:
              count += 1
          # 当前元素不等于主要元素时，计数器-1
          else:
              count -= 1

      # 当已知条件中包括多数元素一定超过半数或一定存在多数元素时，可省略阶段二
      # 阶段二：统计阶段一结果的具体票数
      check_count = 0
      for num in nums:
          if result == num:
              check_count += 1

      # 超过半数，即结果合法
      if check_count > len(nums)/2:
          return result
      # 结果不合法，无符合条件的结果
      else:
        return None

算法描述

实现步骤

过程梳理

伪代码

具体实现

其他补充

算法应用

求主要/多数元素

参考资料

摩尔计数法

# 算法描述

# 实现步骤

# 过程梳理

# 伪代码

# 具体实现

# 其他补充

# 算法应用

# 求主要/多数元素

# 参考资料

算法描述

实现步骤

过程梳理

伪代码

具体实现

其他补充

算法应用

求主要/多数元素

参考资料