169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。

多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

n == nums.length
1 <= 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存在，返回其计数；否则返回默认值0int 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)) {// 键存在，取出旧值并加 1int oldCount = countMap.get(num);countMap.put(num, oldCount + 1);
} else {// 键不存在，初始化为 1countMap.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// - 如果不等，说明遇到了反对者，票数-1count += (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（当前候选人）：null
- count（当前票数）：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;  // 不存在多数元素
}