哪吒2的“多数元素”大冒险：从暴力到优雅，一场算法的修炼之旅
引言
大家好，我是哪吒2，今天我要带大家解决一个看似简单但暗藏玄机的问题——多数元素。这个问题就像是我在陈塘关遇到的妖怪一样，表面上看起来平平无奇，但如果你不用对方法，可能会被它打得满地找牙。
问题的描述是这样的：给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于 n/2 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
听起来很简单对吧？但别急，我们得用多种方法来解决它，就像我在电影里用风火轮、混天绫、乾坤圈一样，每种武器都有它的用武之地！
方法一：暴力解法——哪吒的“蛮力拳”
思路
首先，哪吒2决定用最直接的方法——暴力枚举。遍历数组中的每一个元素，然后统计它在数组中出现的次数。如果某个元素的出现次数大于 n/2，那它就是我们要找的多数元素。
代码实现
java
public int majorityElement(int[] nums) {
int n = nums.length;
for (int num : nums) {
int count = 0;
for (int otherNum : nums) {
if (num == otherNum) {
count++;
}
}
if (count > n / 2) {
return num;
}
}
return -1; // 题目保证有解，这里不会执行
}分析
- 时间复杂度：O(n^2)，因为我们需要对每个元素遍历整个数组。
- 空间复杂度：O(1)，只用了常数级别的额外空间。
哪吒的吐槽
“这方法虽然简单，但效率太低了！就像我用蛮力打妖怪，虽然能赢，但累得半死。有没有更高效的方法呢？”
方法二：哈希表——哪吒的“混天绫”
思路
哪吒2决定用哈希表来优化。我们可以用一个哈希表来记录每个元素出现的次数，然后遍历哈希表找到出现次数大于 n/2 的元素。
代码实现
java
import java.util.HashMap;
import java.util.Map;
public int majorityElement(int[] nums) {
Map map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (Map.Entry entry : map.entrySet()) {
if (entry.getValue() > nums.length / 2) {
return entry.getKey();
}
}
return -1; // 题目保证有解，这里不会执行
} 分析
- 时间复杂度：O(n)，遍历数组和哈希表各一次。
- 空间复杂度：O(n)，哈希表需要存储所有元素的出现次数。
哪吒的吐槽
“这个方法比暴力解法快多了！就像我用混天绫捆住妖怪，轻松搞定。但有没有更省空间的方法呢？”
方法三：排序法——哪吒的“乾坤圈”
思路
哪吒2灵机一动，想到了排序。如果将数组排序，那么多数元素一定会出现在数组的中间位置（因为它的数量超过一半）。
代码实现
java
import java.util.Arrays;
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}分析
- 时间复杂度：O(n log n)，排序的时间复杂度。
- 空间复杂度：O(1)，如果使用原地排序算法。
哪吒的吐槽
“这个方法简单又高效！就像我用乾坤圈直接砸中妖怪的要害。但有没有时间复杂度更低的方法呢？”
方法四：摩尔投票法——哪吒的“风火轮”
思路
哪吒2终于拿出了他的终极武器——摩尔投票法。这个方法的核心思想是：多数元素的数量比其他所有元素的总和还要多。我们可以用一个变量 candidate 来记录当前的候选多数元素，用另一个变量 count 来记录它的出现次数。遍历数组时，如果当前元素等于 candidate，则 count++，否则 count--。如果 count 减到 0，就更换 candidate。
代码实现
java
public int majorityElement(int[] nums) {
int candidate = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (count == 0) {
candidate = nums[i];
count = 1;
} else if (nums[i] == candidate) {
count++;
} else {
count--;
}
}
return candidate;
}分析
- 时间复杂度：O(n)，只需要遍历一次数组。
- 空间复杂度：O(1)，只用了常数级别的额外空间。
哪吒的吐槽
“这才是真正的神器！就像我用风火轮瞬间飞到妖怪面前，一击必杀。摩尔投票法不仅高效，还省空间，简直是算法的巅峰之作！”
方法五：分治法——哪吒的“三头六臂”
思路
哪吒2决定挑战一下自己，用分治法来解决这个问题。将数组分成左右两部分，分别求出左半部分的多数元素和右半部分的多数元素。如果左右两部分的多数元素相同，则直接返回；否则，统计这两个元素在整个数组中的出现次数，返回出现次数较多的那个。
代码实现
java
public int majorityElement(int[] nums) {
return divideAndConquer(nums, 0, nums.length - 1);
}
private int divideAndConquer(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = left + (right - left) / 2;
int leftMajority = divideAndConquer(nums, left, mid);
int rightMajority = divideAndConquer(nums, mid + 1, right);
if (leftMajority == rightMajority) {
return leftMajority;
}
int leftCount = countInRange(nums, leftMajority, left, right);
int rightCount = countInRange(nums, rightMajority, left, right);
return leftCount > rightCount ? leftMajority : rightMajority;
}
private int countInRange(int[] nums, int target, int left, int right) {
int count = 0;
for (int i = left; i <= right; i++) {
if (nums[i] == target) {
count++;
}
}
return count;
}分析
- 时间复杂度：O(n log n)，分治法的时间复杂度。
- 空间复杂度：O(log n)，递归栈的深度。
哪吒的吐槽
“分治法虽然有点复杂，但它的思想很深刻！就像我用三头六臂同时对付多个妖怪，虽然累，但很有成就感。”
总结
通过这次“多数元素”大冒险，哪吒2学会了多种解决问题的方法。从暴力解法到摩尔投票法，每一种方法都有它的独特之处。就像我在电影里用不同的武器对付不同的妖怪一样，算法也需要根据问题的特点选择合适的方法。
最后，哪吒2想对大家说：“算法的修炼之路就像我的成长之路，充满了挑战和乐趣。只要坚持不懈，你一定能找到属于自己的‘风火轮’！”
思考题
- 如果数组中没有保证存在多数元素，你会如何修改算法？
- 你能想到其他解决“多数元素”问题的方法吗？
- 分治法的时间复杂度为什么是 O(n log n)？你能证明吗？
希望这篇文章能给你带来一些启发，也欢迎大家在评论区分享你的想法和经验。我们下次再见！