esc to dismiss

摩尔投票

摩尔投票算法(Boyer–Moore majority vote algorithm) 又叫多数投票算法。

摩尔投票算法是在一组数据中找出占多数(超过一半以上)的元素的方法,其时间复杂度为 O(n), 空间复杂度为 O(1). 其具体做法是:

对于一组数据 nums,设定候选元素变量 m, 计数变量 c,遍历 nums 的每一个元素(变量 n):

  • 如果 c == 0, 则 m = n, c = 1

  • 如果 m == n, 则 c = c+1

  • 否则 m ≠ n , 则 c = c-1

最后得到的 m 即为所求元素。但如果元素中不确定是否存在超过半数的元素时,还需再遍历一次 nums,将 m 与各元素比较,看出现次数是否超过半数。因此,需要两次遍历

摩尔算法其实也挺好理解,即选一个元素,然后比较下一个元素,如果不一样就消掉,这样留在最后的肯定是超过半数的元素。

对于例子,可参考 面试题 17.10. 主要元素 ,并可以参考里面的图解。

x