摩尔投票法

摩尔投票法

摩尔投票法的核心思想为对拼消耗。

每次从序列里选择两个不相同的数字删除掉(或称为「抵消」),最后剩下一个数字或几个相同的数字,就是出现次数大于总数一半的那个元素。

首先我们考虑最基本的摩尔投票问题,比如找出一组数字序列中出现次数大于总数21的数字(并且假设这个数字一定存在)。