1.题目基本信息

1.1.题目描述

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

1.2.题目地址

https://leetcode.cn/problems/majority-element-ii/description/

2.解题方法

2.1.解题思路

摩尔投票算法

2.2.解题步骤

第一步，使用投票算法，选出两个个数可能超过1/3的候选人

第二步，验证个数是否超过1/3，并将超过1/3的候选数加到结果数组中进行返回

3.解题代码

python代码

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # 思路：摩尔投票算法
        # 第一步，使用投票算法，选出两个个数可能超过1/3的候选人
        candidate1, candidate2 = nums[0], nums[0]
        vote1, vote2 = 0, 0
        for num in nums:
            if vote1 > 0 and candidate1 == num:
                vote1 += 1
            elif vote2 > 0 and candidate2 == num:
                vote2 += 1
            elif vote1 == 0:
                candidate1 = num
                vote1 = 1
            elif vote2 == 0:
                candidate2 = num
                vote2 = 1
            else:
                # 都不相等情况，且投票数都大于0，则进行抵消
                vote1 -= 1
                vote2 -= 1
        # 第二步，验证个数是否超过1/3，并将超过1/3的候选数加到结果数组中进行返回
        cnt1, cnt2 = 0, 0
        for num in nums:
            if vote1 > 0 and num == candidate1:
                cnt1 += 1
            elif vote2 > 0 and num == candidate2:
                cnt2 += 1
        result = []
        if cnt1 * 3 > len(nums):
            result.append(candidate1)
        if cnt2 * 3 > len(nums):
            result.append(candidate2)
        return result

4.执行结果