摩尔投票法

给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/2 ⌋ 次的元素。

示例 1:

输入:nums = [1]
输出:[1]

分析:采用摩尔投票法,两个阶段:抵消阶段和技术阶段

抵消阶段:两个不同投票进行对坑,并且同时抵消掉各一张票,如果两个投票相同,则累加可抵消的次数;

以 [2,2,1,3,1,2,2] 为例

计数阶段:在抵消阶段最后得到的抵消计数只要不为 0,那这个候选人是有可能超过一半的票数的,为了验证,则需要遍历一次,统计票数,才可确定

时间复杂度为 O(n)

原文地址:https://www.cnblogs.com/chenweibo/p/13762366.html