[已解决]请教一下摩尔计票法

酷酷的枪手

摩尔计数法应用于在一个列表中找出现次数大于1/2的元素我理解了，但是在这一题里摩尔计票法的原理我不是很理解。

最佳答案

月排行榜 / 总排行榜

不二猫猫

2023-3-14 23:13:04

摩尔投票法的原理是从一个序列中找出出现次数超过一半的元素。具体来说，算法维护一个候选元素 candidate 和一个计数器 count，初始时 candidate 可以为任何元素，count 为 0。遍历整个序列，对于每个元素，如果 count 为 0，则将 candidate 设为当前元素，然后将 count 设为 1；否则如果当前元素等于 candidate，则将 count 加 1，否则将 count 减 1。遍历完整个序列后，candidate 中存储的元素就是出现次数超过一半的元素。

这个算法的核心思想是抵消。如果一个元素的出现次数超过一半，那么将其与其他元素一一抵消，最后剩下的一定是该元素。例如对于序列 [1, 1, 1, 2, 2]，我们可以将 1 和 2 一一抵消，最后剩下的是 1。如果序列中不存在出现次数超过一半的元素，那么最后剩下的元素也不一定是候选元素，需要再次遍历序列验证。

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。由于算法只需要遍历一次序列，因此它比其他基于排序或哈希表的算法具有更高的效率和更小的空间占用。

跳转到最佳答案楼层

不二猫猫

摩尔投票法的原理是从一个序列中找出出现次数超过一半的元素。具体来说，算法维护一个候选元素 candidate 和一个计数器 count，初始时 candidate 可以为任何元素，count 为 0。遍历整个序列，对于每个元素，如果 count 为 0，则将 candidate 设为当前元素，然后将 count 设为 1；否则如果当前元素等于 candidate，则将 count 加 1，否则将 count 减 1。遍历完整个序列后，candidate 中存储的元素就是出现次数超过一半的元素。

这个算法的核心思想是抵消。如果一个元素的出现次数超过一半，那么将其与其他元素一一抵消，最后剩下的一定是该元素。例如对于序列 [1, 1, 1, 2, 2]，我们可以将 1 和 2 一一抵消，最后剩下的是 1。如果序列中不存在出现次数超过一半的元素，那么最后剩下的元素也不一定是候选元素，需要再次遍历序列验证。

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。由于算法只需要遍历一次序列，因此它比其他基于排序或哈希表的算法具有更高的效率和更小的空间占用。