代码训练(18)LeetCode之多数元素

Author: Once Day Date: 2024年9月13日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 169. 多数元素 - 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

1. 原题

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

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

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

示例 1：

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

示例 2：

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

2. 分析

本题目要求找出一个数组中的多数元素，即出现次数大于数组长度一半的元素。题目保证了这样的元素总是存在。

常见解题方法：

• 哈希表法：使用哈希表记录每个元素的出现次数，然后遍历哈希表找到出现次数大于 n/2 的元素。这种方法的时间复杂度是 O(n)，但空间复杂度也是 O(n)。
• 排序法：将数组排序，中间的元素（索引为 n/2）必为多数元素。时间复杂度是 O(nlogn)，因为排序的平均时间复杂度为 O(nlogn)，空间复杂度取决于排序实现，通常为 O(1) 到 O(n)。
• 摩尔投票法（Boyer-Moore Voting Algorithm）：这是一种时间复杂度为 O(n) 且空间复杂度为 O(1) 的优秀算法。基本思想是两两抵消不同的元素，最后剩下的元素可能是多数元素。

这里将展开摩尔投票法的具体实现步骤：

1. 初始化一个候选人candidate和计数器count为0。
2. 遍历数组中的每个元素x:
   • 如果count为0，则将candidate设置为x，count设置为1。
   • 如果x等于candidate，则count加1。
   • 否则，count减1。
3. 经过上述过程，candidate应该是多数元素。

性能优化关键点：

• 摩尔投票法在时间和空间复杂度上是最优的，时间复杂度为 O(n)，空间复杂度为 O(1)。
• 由于这种算法不需要额外的存储空间（除了几个基本变量），它特别适合处理大数据量的问题。

3. 代码实现

#include <stdio.h>int majorityElement(int* nums, int numsSize) {int candidate = 0;int count = 0;for (int i = 0; i < numsSize; i++) {if (count == 0) {candidate = nums[i];}if (nums[i] == candidate) {count++;} else {count--;}}return candidate;
}

这个函数的作用是寻找一个整数数组中的多数元素，即在数组中出现次数超过一半的元素。函数采用了一种名为“摩尔投票算法”（Boyer-Moore Voting Algorithm）的高效方法来实现这一目标。

摩尔投票算法的核心思想是通过一系列的比较和计数来找到可能的候选者，然后验证这个候选者是否真的是多数元素。具体到这个函数，它首先初始化两个变量：candidate用于存储当前的候选者，而count用于记录这个候选者的计数值。

函数的处理流程大致如下：

1. 遍历输入数组nums，数组的大小为numsSize。
2. 对于每个元素nums[i]，首先检查count是否为0。如果为0，说明前面的所有候选者都被完全抵消了，需要重新选取当前元素作为新的候选者，并重置计数为1。
3. 接下来验证当前元素是否等于候选者candidate:
   • 如果相等，则增加count的值，表示候选者获得了支持。
   • 如果不等，则减少count的值，表示候选者失去了一些支持。
4. 经过一轮完整的遍历后，candidate变量中存储的就是数组中的多数元素。

这个算法的优势在于它的时间复杂度为O(n)，空间复杂度为O(1)，非常适合处理大数据集。它巧妙地通过抵消机制避免了需要额外存储空间来记录每个元素的出现次数，而是直接在遍历过程中确定可能的多数元素。

4. 总结

对编程能力的考查主要集中在对数组操作的理解和算法效率的优化上。通过此题，可以加深对线性时间算法设计的理解，尤其是摩尔投票算法的巧妙之处。