给定一个大小为 n 的数组 nums ，返回其中的多数元素。
多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
我的想法：
之前一眼hash的时候用的是异或，这个题目不是简单的计数，所以大概hash也是可行的吧，嗯...异或只能判断出现的奇偶性。
1 分析一下异或，hash的解法可行性
你的想法尝试使用哈希或异或操作来解决问题，不过这两种方法在这个问题上有一些限制：
1. 异或操作的局限性
你提到 "异或只能判断出现的奇偶性"，这是正确的。异或（XOR）的性质是：
- 相同元素异或结果为 0（如
a ^ a = 0） - 任何元素与 0 异或结果为自身（如
a ^ 0 = a）
因此，如果一个元素出现奇数次，异或结果会保留该元素；但如果出现偶数次，异或结果会抵消为 0。然而，这个问题要求的是 " 出现次数大于 n/2" 的元素，而异或无法直接统计次数或比较频率，所以异或在这里不适用。
2. 哈希表的正确用法
虽然你提到 "hash 也是可行的吧"，但需要注意哈希表的具体用法：
- 错误用法：若用哈希表存储元素的异或结果，无法解决问题（与直接异或数组相同）。
- 正确用法：用哈希表统计每个元素的出现次数，然后遍历哈希表找到次数超过 n/2 的元素。
例如：
java
运行
import java.util.HashMap;
import java.util.Map;
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
if (entry.getValue() > nums.length / 2) {
return entry.getKey();
}
}
return -1; // 题目保证存在多数元素，不会执行到这里
}
}
这个方法的时间和空间复杂度都是 O (n)，符合题目要求，但不是最优解。
3. 最优解法：摩尔投票法（Boyer-Moore Voting Algorithm）
如果追求 O (1) 空间复杂度，可以使用摩尔投票法：
java
运行
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
原理：
- 遍历数组时维护一个候选元素
candidate和计数器count。 - 遇到与
candidate相同的元素，count +1；否则count -1。 - 当
count减为 0 时，更换候选元素为当前元素。 - 由于多数元素出现次数超过一半，最终候选元素一定是多数元素。
总结
你的方向（哈希或异或）有一定合理性，但需要注意：
- 异或无法直接解决该问题，因为它不统计次数，只判断奇偶性。
- 哈希表需要用于统计次数，而不是异或操作。
- 摩尔投票法是最优解，满足 O (n) 时间和 O (1) 空间。
2 hash表解法
import java.util.HashMap;
import java.util.Map;
class Solution {
public int majorityElement(int[] nums) {
// 1. 创建一个哈希表，键为数组中的元素，值为该元素出现的次数
Map<Integer, Integer> countMap = new HashMap<>();
// 2. 遍历数组中的每个元素
for (int num : nums) {
// 3. 对于当前元素num，获取它在哈希表中已有的计数
// getOrDefault方法：如果num存在，返回其计数；否则返回默认值0
int currentCount = countMap.getOrDefault(num, 0);
// 4. 将当前元素的计数加1，并更新到哈希表中
// put方法：将键值对 (num, currentCount + 1) 存入哈希表
// 如果键num已存在，会覆盖旧值；如果不存在，则创建新的键值对
countMap.put(num, currentCount + 1);
}
// 5. 遍历哈希表，找出出现次数超过数组长度一半的元素
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
// entry.getKey() 返回当前键（元素值）
// entry.getValue() 返回当前值（出现次数）
if (entry.getValue() > nums.length / 2) {
return entry.getKey();
}
}
// 根据题目假设，数组中总是存在多数元素，因此不会执行到这里
return -1;
}
}关于put方法的详细解释
put是 HashMap 类的核心方法，用于存储或更新键值对：
java
运行
map.put(key, value);
功能：
- 如果
key不存在于哈希表中：创建新的键值对(key, value)。 - 如果
key已存在：用新的value覆盖旧值（旧值会被丢弃）。
- 如果
示例：
java
运行
Map<String, Integer> scores = new HashMap<>(); scores.put("Alice", 90); // 添加新键值对：Alice -> 90 scores.put("Bob", 85); // 添加新键值对：Bob -> 85 scores.put("Alice", 95); // 更新已有键：Alice -> 95（旧值90被覆盖）在本题中的作用：
java
运行
countMap.put(num, currentCount + 1);这行代码会将元素
num的计数更新为currentCount + 1，无论num之前是否存在于哈希表中。
复杂度分析
- 时间复杂度：O (n) —— 遍历数组一次，遍历哈希表一次。
- 空间复杂度：O (n) —— 最坏情况下，哈希表需要存储所有元素。
getOrDefault 是 Java 中 Map 接口提供的一个实用方法，用于安全地获取键对应的值，避免 NullPointerException。我来详细解释它的用法和在这个问题中的作用。
getOrDefault 方法详解
方法签名
java
运行
V getOrDefault(Object key, V defaultValue);
- 参数：
key：要查找的键。defaultValue：如果键不存在时返回的默认值。
- 返回值：
- 如果键存在，返回对应的值；
- 如果键不存在，返回
defaultValue。
为什么需要 getOrDefault？
在统计元素次数时，传统写法需要先检查键是否存在，不存在则初始化为 0，存在则加 1：
java
运行
// 传统写法（不使用 getOrDefault）
if (countMap.containsKey(num)) {
// 键存在，取出旧值并加 1
int oldCount = countMap.get(num);
countMap.put(num, oldCount + 1);
} else {
// 键不存在，初始化为 1
countMap.put(num, 1);
}
使用 getOrDefault 可以简化这个逻辑，一行代码完成统计：
java
运行
// 等效写法（使用 getOrDefault）
int currentCount = countMap.getOrDefault(num, 0); // 不存在则默认 0
countMap.put(num, currentCount + 1); // 直接更新计数
在多数元素问题中的应用
让我结合原题代码，逐行解释 getOrDefault 的作用：
java
运行
import java.util.HashMap;
import java.util.Map;
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
// 1. 获取当前元素 num 的已有计数
// 如果 num 第一次出现，getOrDefault 返回默认值 0
// 如果 num 已存在，返回其当前计数
int currentCount = countMap.getOrDefault(num, 0);
// 2. 将计数加 1 后存入哈希表
// 如果 num 是第一次出现，这行代码会创建新的键值对 (num, 1)
// 如果 num 已存在，这行代码会覆盖旧值，更新为新的计数
countMap.put(num, currentCount + 1);
}
// ...后续代码不变...
}
}
对比实验：理解 getOrDefault 的行为
假设我们有一个空的哈希表 countMap，执行以下操作：
java
运行
Map<Integer, Integer> countMap = new HashMap<>();
// 第一次遇到元素 3
int count1 = countMap.getOrDefault(3, 0); // 返回 0（键不存在）
countMap.put(3, count1 + 1); // 存入 (3, 1)
// 第二次遇到元素 3
int count2 = countMap.getOrDefault(3, 0); // 返回 1（键已存在）
countMap.put(3, count2 + 1); // 存入 (3, 2)
// 最终哈希表中：{3=2}
其他常见用法场景
统计字符串中字符出现次数：
java
运行
String s = "hello"; Map<Character, Integer> charCount = new HashMap<>(); for (char c : s.toCharArray()) { charCount.put(c, charCount.getOrDefault(c, 0) + 1); } // 结果：{h=1, e=1, l=2, o=1}分组统计：
java
运行
List<String> words = Arrays.asList("apple", "banana", "apple"); Map<Integer, Integer> lengthCount = new HashMap<>(); for (String word : words) { int length = word.length(); lengthCount.put(length, lengthCount.getOrDefault(length, 0) + 1); } // 结果：{5=1, 6=2}（长度为5的单词1个，长度为6的单词2个）
总结
getOrDefault 是处理哈希表计数问题的 “语法糖”，它的核心优势是：
- 简化代码：避免了手动检查键是否存在的繁琐逻辑。
- 防止空指针异常：当键不存在时返回默认值（如 0），而不是
null。 - 代码可读性：让统计逻辑更加清晰直观。
在处理需要初始化默认值的场景时，它是 Java 程序员的常用工具之一！
3 摩尔投票法（Boyer-Moore Voting Algorithm）
摩尔投票法（Boyer-Moore Voting Algorithm），这个算法的核心思想可以用一句话概括："多数元素在数组中出现的次数超过一半，因此即使与其他所有元素两两抵消，最终也会剩下至少一个自身"。
class Solution {
public int majorityElement(int[] nums) {
// 初始化计数器，用于记录当前候选人的票数
int count = 0;
// 初始化候选人，Integer类型允许为null，表示尚未选出候选人
Integer candidate = null;
// 遍历数组中的每个元素
for (int num : nums) {
// 当计数器为0时，意味着当前候选人的票数已被完全抵消
// 需要选择当前元素作为新的候选人
if (count == 0) {
candidate = num;
}
// 根据当前元素是否等于候选人来更新计数器：
// - 如果相等，说明遇到了支持者，票数+1
// - 如果不等，说明遇到了反对者，票数-1
count += (num == candidate) ? 1 : -1;
}
// 遍历结束后，最终的候选人即为多数元素
// 由于多数元素的数量超过n/2，即使中途被抵消，最终也会胜出
return candidate;
}
}核心逻辑解释
候选人交替：
- 当
count减为 0 时，说明当前候选人的支持票被反对票完全抵消，此时需要更换候选人为当前元素。
- 当
票数更新：
- 遇到与候选人相同的元素时，
count增加 1（支持票） - 遇到与候选人不同的元素时，
count减少 1（反对票）
- 遇到与候选人相同的元素时，
最终胜利条件：
- 由于多数元素的出现次数超过一半，即使在遍历过程中被其他元素抵消，最终也会因为自身数量优势重新成为候选人并保持到最后。
算法核心思想
想象一场投票选举，每个候选人需要和对手 "一对一拼消耗"：
- 每次遇到自己的支持者，票数
+1； - 每次遇到对手，票数
-1； - 当票数减为
0时，当前候选人 "下台"，由新的候选人接替。
由于多数元素的支持者超过半数，即使其他所有候选人联合起来抵消票数，多数元素最终仍会胜出。
算法步骤拆解
我们用数组 [2, 2, 1, 1, 1, 2, 2] 为例，逐步演示算法过程：
初始化：
candidate（当前候选人）：nullcount（当前票数）：0
遍历数组：
第 1 个元素
2：- 当前
count = 0，任命2为新候选人，count +1→1。 - 状态：
candidate = 2,count = 1。
- 当前
第 2 个元素
2：- 与候选人相同，
count +1→2。 - 状态：
candidate = 2,count = 2。
- 与候选人相同，
第 3 个元素
1：- 与候选人不同，
count -1→1。 - 状态：
candidate = 2,count = 1。
- 与候选人不同，
第 4 个元素
1：- 与候选人不同，
count -1→0。 - 状态：
candidate = 2,count = 0（候选人下台）。
- 与候选人不同，
第 5 个元素
1：- 当前
count = 0，任命1为新候选人，count +1→1。 - 状态：
candidate = 1,count = 1。
- 当前
第 6 个元素
2：- 与候选人不同，
count -1→0。 - 状态：
candidate = 1,count = 0（候选人下台）。
- 与候选人不同，
第 7 个元素
2：- 当前
count = 0，任命2为新候选人，count +1→1。 - 状态：
candidate = 2,count = 1。
- 当前
遍历结束：最终候选人是
2，返回2。
代码实现（Java）
java
运行
class Solution {
public int majorityElement(int[] nums) {
int count = 0; // 记录当前候选人的票数
Integer candidate = null; // 当前候选人（初始为 null）
for (int num : nums) {
// 当票数为 0 时，更换候选人
if (count == 0) {
candidate = num;
}
// 根据当前元素是否等于候选人，更新票数
count += (num == candidate) ? 1 : -1;
}
return candidate; // 最终剩下的候选人即为多数元素
}
}
关键细节解释
为什么
count = 0时更换候选人？- 当
count = 0时，说明当前候选人的票数已被完全抵消，需要重新选择候选人。 - 由于多数元素的数量超过一半，即使中途被其他元素抵消，最终仍会重新成为候选人并胜出。
- 当
为什么不需要验证最终候选人？
- 根据算法逻辑，多数元素的数量超过
n/2，因此无论其他元素如何抵消，多数元素最终的票数至少为1。 - 因此，最后剩下的候选人必然是多数元素。
- 根据算法逻辑，多数元素的数量超过
复杂度分析
- 时间复杂度：O (n) —— 只需遍历一次数组。
- 空间复杂度：O (1) —— 只需要常数级的额外空间。
进阶思考：如果没有多数元素会怎样？
如果数组中不存在多数元素，摩尔投票法会返回一个错误的结果。例如：
- 数组
[1, 2, 3]：最终返回3，但3并不是多数元素。
因此，如果题目没有明确保证存在多数元素，需要在算法结束后额外验证最终候选人是否真的超过半数：
java
运行
// 增加验证步骤
int candidate = majorityElement(nums); // 调用摩尔投票法
int count = 0;
for (int num : nums) {
if (num == candidate) count++;
}
if (count > nums.length / 2) {
return candidate;
} else {
return -1; // 不存在多数元素
}
总结
摩尔投票法的美在于：
- 无需额外空间：通过巧妙的抵消策略，直接在遍历中找出多数元素。
- 线性时间复杂度：一次遍历即可完成，效率极高。
- 思想深刻：将问题转化为 "投票抵消" 模型，直观且优雅。
这个算法在处理大规模数据时尤为高效，是面试中的高频考点，建议反复理解其核心思想！