面试题_主要元素.org

题目

思路

摩尔投票法

核心是对拼消耗

找出一组数字序列中出现次数大于总数1/2的数字（并且假设这个数字一定存在）；则每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个

code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        if not nums: return -1
        if len(nums) == 1: return nums[0]
        if len(list(nums)) == len(set(nums)): return -1 # 一定没有主要元素（排除摩尔投票法不满足的特例）

        tmp = nums[0]
        cot = 1
        for num in nums[1:]:
            if num == tmp:
                cot += 1
            else:
                cot -= 1
                if cot == 0:
                    tmp = num # 更新可能是主要元素的值
                    cot = 1
        if cot > 0:
            return tmp