LeetCode 多数元素II题解
题目描述
给定一个整数数组，找出所有出现次数超过 ⌊ n/3 ⌋ 的元素。
示例：
输入：nums = [1,1,1,3,2,2,2]
输出：[1,2]
解题思路
方法： Boyer-Moore 投票算法
思路：
- 使用 Boyer-Moore 投票算法的扩展版本。
- 最多有 2 个元素出现次数超过 n/3。
- 先找出可能的候选元素，再验证。
复杂度分析：
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
代码实现
def majority_element_ii(nums): if not nums: return [] candidate1 = candidate2 = None count1 = count2 = 0 for num in nums: if candidate1 == num: count1 += 1 elif candidate2 == num: count2 += 1 elif count1 == 0: candidate1 = num count1 = 1 elif count2 == 0: candidate2 = num count2 = 1 else: count1 -= 1 count2 -= 1 count1 = count2 = 0 for num in nums: if num == candidate1: count1 += 1 elif num == candidate2: count2 += 1 result = [] n = len(nums) if count1 > n // 3: result.append(candidate1) if count2 > n // 3: result.append(candidate2) return result # 测试 def test_majority_element_ii(): nums = [1, 1, 1, 3, 2, 2, 2] print(majority_element_ii(nums)) # 输出：[1, 2] if __name__ == "__main__": test_majority_element_ii()总结
多数元素II是 Boyer-Moore 投票算法的扩展应用，找出所有出现次数超过 n/3 的元素。
