229. 多数元素 II
题目描述
输入一个长度为 n 的整数数组 nums。
找出所有出现次数严格大于 ⌊n / 3⌋ 的数，把它们放进一个列表返回。列表中每个数只出现一次，顺序不限。没有这样的数时返回空列表。
示例 1
输入：nums = [3,2,3] 输出：[3]
解释：n = 3，⌊3/3⌋ = 1，3 出现了 2 次，超过 1。
示例 2
输入：nums = [1] 输出：[1]
解释：只有一个元素，出现 1 次，超过 ⌊1/3⌋ = 0。
示例 3
输入：nums = [1,2] 输出：[1,2]
解释：1 和 2 各出现 1 次，都超过 ⌊2/3⌋ = 0。
数据范围
1 <= nums.length <= 5 * 10^4-10^9 <= nums[i] <= 10^9
进阶：能否在 O(n) 时间内只用 O(1) 额外空间完成？
解题思路：摩尔投票
出现次数超过 n/3 的元素最多只有 2 个。用哈希表计数需要 O(n) 空间；摩尔投票只保留 2 个候选和各自的票数：遇到候选就加票，有空位就占位，否则三个不同的数“两两抵消”，让两个候选各减一票。每次抵消会去掉 3 个互不相同的数，真正的多数元素不可能被抵消光，所以最后一定留在候选里。最后再扫一遍数组，验证候选是否真的超过 n/3。
为什么正确
每次抵消都删掉 3 个互不相同的元素；出现次数超过 n/3 的元素无法被全部删掉，因此结束时必在候选 c1、c2 之中。
复杂度分析
时间 O(n)（投票一遍 + 验证一遍），额外空间 O(1)。
易错点
投票结束后的候选只是“可能”的答案，必须再数一遍。例如 [1,2,3] 结束时候选非空，但没有任何元素超过 n/3。另外 x 要先和两个候选比较，再判断空位，否则同一个数可能同时占据两个候选。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
c1, c2, n1, n2 = None, None, 0, 0
for x in nums:
if x == c1:
n1 += 1
elif x == c2:
n2 += 1
elif n1 == 0:
c1, n1 = x, 1
elif n2 == 0:
c2, n2 = x, 1
else:
n1 -= 1
n2 -= 1
return [c for c in (c1, c2) if nums.count(c) > len(nums) // 3]class Solution {
public List<Integer> majorityElement(int[] nums) {
long c1 = Long.MIN_VALUE, c2 = Long.MIN_VALUE;
int n1 = 0, n2 = 0;
for (int x : nums) {
if (x == c1) {
n1++;
} else if (x == c2) {
n2++;
} else if (n1 == 0) {
c1 = x; n1 = 1;
} else if (n2 == 0) {
c2 = x; n2 = 1;
} else {
n1--;
n2--;
}
}
List<Integer> res = new ArrayList<>();
for (long c : new long[]{c1, c2}) {
int cnt = 0;
for (int y : nums) if (y == c) cnt++;
if (cnt > nums.length / 3) res.add((int) c);
}
return res;
}
}class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
long long c1 = LLONG_MIN, c2 = LLONG_MIN;
int n1 = 0, n2 = 0;
for (int x : nums) {
if (x == c1) {
n1++;
} else if (x == c2) {
n2++;
} else if (n1 == 0) {
c1 = x; n1 = 1;
} else if (n2 == 0) {
c2 = x; n2 = 1;
} else {
n1--;
n2--;
}
}
vector<int> res;
for (long long c : {c1, c2})
if (count(nums.begin(), nums.end(), c) > (long long)nums.size() / 3) res.push_back((int)c);
return res;
}
};func majorityElement(nums []int) []int {
c1, c2, n1, n2 := math.MinInt64, math.MinInt64, 0, 0
for _, x := range nums {
if x == c1 {
n1++
} else if x == c2 {
n2++
} else if n1 == 0 {
c1, n1 = x, 1
} else if n2 == 0 {
c2, n2 = x, 1
} else {
n1--
n2--
}
}
res := []int{}
for _, c := range []int{c1, c2} {
cnt := 0
for _, y := range nums {
if y == c {
cnt++
}
}
if cnt > len(nums)/3 {
res = append(res, c)
}
}
return res
}var majorityElement = function(nums) {
let c1 = null, c2 = null, n1 = 0, n2 = 0;
for (const x of nums) {
if (x === c1) {
n1++;
} else if (x === c2) {
n2++;
} else if (n1 === 0) {
c1 = x; n1 = 1;
} else if (n2 === 0) {
c2 = x; n2 = 1;
} else {
n1--;
n2--;
}
}
return [c1, c2].filter(c => nums.filter(y => y === c).length > Math.floor(nums.length / 3));
};function majorityElement(nums: number[]): number[] {
let c1: number | null = null, c2: number | null = null, n1 = 0, n2 = 0;
for (const x of nums) {
if (x === c1) {
n1++;
} else if (x === c2) {
n2++;
} else if (n1 === 0) {
c1 = x; n1 = 1;
} else if (n2 === 0) {
c2 = x; n2 = 1;
} else {
n1--;
n2--;
}
}
return [c1, c2].filter(c => c !== null && nums.filter(y => y === c).length > Math.floor(nums.length / 3)) as number[];
}其他解法
哈希表计数最直观但占 O(n) 空间；摩尔投票利用“最多两个答案”的性质把空间降到 O(1)，但需要第二遍验证候选人。
解法 2：哈希表计数 时间 O(n)，空间 O(n)
用哈希表统计每个数出现的次数。遍历哈希表，把次数大于 ⌊n/3⌋ 的数加入答案。
思路直接，不容易写错。需要 O(n) 额外空间，不满足进阶要求的 O(1) 空间。
from collections import Counter
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
cnt = Counter(nums)
return [x for x, c in cnt.items() if c > len(nums) // 3]class Solution {
public List<Integer> majorityElement(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) cnt.merge(x, 1, Integer::sum);
List<Integer> res = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : cnt.entrySet())
if (e.getValue() > nums.length / 3) res.add(e.getKey());
return res;
}
}class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
vector<int> res;
for (auto& [x, c] : cnt)
if (c > (int)nums.size() / 3) res.push_back(x);
return res;
}
};func majorityElement(nums []int) []int {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
res := []int{}
for x, c := range cnt {
if c > len(nums)/3 {
res = append(res, x)
}
}
return res
}var majorityElement = function(nums) {
const cnt = new Map();
for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
const res = [];
for (const [x, c] of cnt)
if (c > Math.floor(nums.length / 3)) res.push(x);
return res;
};function majorityElement(nums: number[]): number[] {
const cnt = new Map<number, number>();
for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
const res: number[] = [];
for (const [x, c] of cnt)
if (c > Math.floor(nums.length / 3)) res.push(x);
return res;
}