84.LeetCode.169. 求众数

• 标签： 数组
• 难度： 简单

---

• 题目描述

追加一条要求： 线性复杂度， 不使用额外空间.

• 我的解法

摩尔投票算法： 每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

从前往后遍历， ans 初始化为第一个数， cnt 代表 ans 出现次数， 初始化为 1, 遍历过程中， 如果某个数不等于 ans, 则互相抵消， cnt 减 1, 如果相等则 cnt 加 1. 若 cnt == 0, 则 ans 换成另一个数，继续往后遍历重复上述过程。遍历完成后， ans 即为众数.

这个过程就像一场壮烈的战斗，伟大革命旗帜交到 第一个人手中， 遇到一个敌人就同归于尽，但是一个人倒下去，另一个人又站起来，继续往下刚。遇到同类，阵营壮大一分。一直到最后，胜利终将是是属于我军的。

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans, cnt = nums[0], 1
        for n in nums[1:]:
            if cnt == 0:
                ans = n
            if ans == n:
                cnt += 1
            else:
                cnt -= 1
        return ans

• 其他解法

暂略。