1. 引言
本文将探讨在Java中查找数组主元素的多种实现方法。主元素（Majority Element）是指在数组中出现次数超过 n/2（n为数组长度）的元素。我们将分析每种方法的代码实现、时间复杂度和空间复杂度，并给出适用场景建议。
2. 问题陈述
给定一个整数数组，我们需要判断是否存在主元素。主元素的定义是：该元素在数组中的出现次数必须严格超过数组长度的一半。例如，在数组 {2, 3, 2, 4, 2, 5, 2} 中，元素 2 出现了4次，而数组长度为7，4 > 7/2，因此 2 是主元素。
本文将使用以下示例数组作为测试用例：
int[] nums = {2, 3, 2, 4, 2, 5, 2};
3. 使用for循环
3.1. 实现
这是最直观的暴力解法：通过双重循环统计每个元素的出现次数。当发现某个元素出现次数超过 n/2 时立即返回。
int majorityThreshold = nums.length / 2;
Integer majorityElement = null;
for (int i = 0; i < nums.length; i++) {
int count = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[i] == nums[j]) {
count++;
}
}
if (count > majorityThreshold) {
majorityElement = nums[i];
break;
}
}
assertEquals(2, majorityElement);
3.2. 复杂度分析
- ⏱️ 时间复杂度：
O(n²)（嵌套循环导致） - 💾 空间复杂度：
O(1)（仅使用常数空间）
✅ 优点：实现简单，无需额外空间
❌ 缺点：性能差，不适用于大数组（当 n>10⁴ 时会明显卡顿）
4. 使用排序方法
4.1. 实现
利用排序后主元素必然占据中间位置的特性：排序后检查中间元素是否满足主元素条件。
Arrays.sort(nums);
int majorityThreshold = nums.length / 2;
int count = 0;
Integer majorityElement = null;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == nums[majorityThreshold]) {
count++;
}
if (count > majorityThreshold) {
majorityElement = nums[majorityThreshold];
break;
}
}
assertEquals(2, majorityElement);
4.2. 复杂度分析
- ⏱️ 时间复杂度：
O(n log n)（主要来自排序） - 💾 空间复杂度：
O(1)或O(n)（取决于排序算法实现）
✅ 优点：代码简洁，比暴力法高效
⚠️ 注意：会修改原数组顺序，且排序开销在超大数据集上仍不可忽视
5. 使用HashMap
5.1. 实现
通过HashMap统计元素频率，线性扫描后检查频率是否超过阈值。
Map<Integer, Integer> frequencyMap = new HashMap<>();
Integer majorityElement = null;
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
int majorityThreshold = nums.length / 2;
for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
if (entry.getValue() > majorityThreshold) {
majorityElement = entry.getKey();
break;
}
}
assertEquals(2, majorityElement);
5.2. 复杂度分析
- ⏱️ 时间复杂度：
O(n)（两次线性遍历） - 💾 空间复杂度：
O(n)（最坏情况存储所有不同元素）
✅ 优点：时间效率高，适合大数据集
❌ 缺点：额外空间开销，内存敏感场景慎用
6. 使用Boyer-Moore投票算法
6.1. 实现
这是最优解法：通过候选者计数机制，在 O(n) 时间和 O(1) 空间内完成。
int majorityThreshold = nums.length / 2;
int candidate = nums[0];
int count = 1;
int majorityElement = -1;
for (int i = 1; i < nums.length; i++) {
if (count == 0) {
candidate = nums[i];
count = 1;
} else if (candidate == nums[i]) {
count++;
} else {
count--;
}
}
count = 0;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
majorityElement = count > majorityThreshold ? candidate : -1;
assertEquals(2, majorityElement);
算法执行过程分解：
初始状态: [候选者(2), 计数(1)]
迭代1: [候选者(2), 计数(0), 元素(3)] // 3≠候选者，计数--
迭代2: [候选者(2), 计数(1), 元素(2)] // 2=候选者，计数++
迭代3: [候选者(2), 计数(0), 元素(4)] // 4≠候选者，计数--
迭代4: [候选者(2), 计数(1), 元素(2)] // 2=候选者，计数++
迭代5: [候选者(2), 计数(0), 元素(5)] // 5≠候选者，计数--
迭代6: [候选者(2), 计数(1), 元素(2)] // 2=候选者，计数++
6.2. 复杂度分析
- ⏱️ 时间复杂度：
O(n)（两次线性遍历） - 💾 空间复杂度：
O(1)（仅用几个变量）
✅ 优点：时间空间双最优，适合超大数据集
⚠️ 注意：需要二次验证（因为算法只保证"可能的主元素"）
7. 方法对比总结
| 方法 | 时间复杂度 | 空间复杂度 | 优缺点 |
|---|---|---|---|
| for循环 | O(n²) | O(1) | ✅ 实现简单 ❌ 性能差，仅适合小数据集 |
| 排序 | O(n log n) | O(1)~O(n) | ✅ 代码简洁 ❌ 修改原数组，排序开销大 |
| HashMap | O(n) | O(n) | ✅ 时间效率高 ❌ 空间开销大 |
| Boyer-Moore算法 | O(n) | O(1) | ✅ 时间空间双最优 ⚠️ 需要二次验证，理解门槛稍高 |
8. 结论
本文分析了四种查找数组主元素的实现方案：
- 暴力法：仅适用于教学或极小数据集，实际开发中应避免
- 排序法：在允许修改原数组且数据量中等时可用
- HashMap法：内存充足时的首选方案，代码清晰易维护
- Boyer-Moore算法：生产环境最优解，尤其适合内存敏感或超大数据场景
💡 开发建议：优先使用Boyer-Moore算法，除非有特殊约束（如不能修改原数组）。对于面试场景，掌握该算法能体现对经典算法的理解深度。
本文所有示例代码可在GitHub仓库中获取。