力扣面试经典——169题

💡 参考代码：

/**
 * 查找数组中的多数元素（出现次数大于⌊n/2⌋的元素）
 * 使用Boyer-Moore投票算法实现
 * 
 * @param nums 整数数组指针
 * @param numsSize 数组长度
 * @return 返回多数元素
 */
int majorityElement(int* nums, int numsSize) {
    // 初始化候选人为第一个元素，计数为1
    int candidate = nums[0];
    int count = 1;
    
    // 投票阶段：遍历数组中剩余的所有元素
    for (int i = 1; i < numsSize; i++) {
        // 如果计数为0，更换候选人
        if (count == 0) {
            candidate = nums[i];  // 设置新的候选人
            count = 1;            // 重置计数为1
        } 
        // 如果当前元素与候选人相同，计数加1
        else if (nums[i] == candidate) {
            count++;
        } 
        // 如果当前元素与候选人不同，计数减1（相当于抵消）
        else {
            count--;
        }
    }
    
    // 返回最终的候选人（多数元素）
    return candidate;
}

📖 总结：

点击展开题目总结

🤔 多数元素

---

1️⃣ 题目核心信息

🎯 功能描述：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

📥 输入输出：

• 输入：int* nums（整数数组指针），int numsSize（数组长度）
• 输出：返回多数元素（保证存在）

---

2️⃣ 实现原理

💡 核心思路：使用Boyer-Moore投票算法，利用多数元素出现次数超过一半的特性，通过"投票抵消"机制找到目标元素。

📋 实现步骤：

1. 初始化候选元素为数组第一个元素，计数器为1
2. 遍历数组剩余元素
3. 若计数器为0，更新候选元素为当前元素，计数器重置为1
4. 若当前元素等于候选元素，计数器加1
5. 若当前元素不等于候选元素，计数器减1
6. 返回最终候选元素

---

3️⃣ 关键点解析

原始思路是使用双重循环统计每个元素出现次数，时间复杂度O(n²)，虽然正确但效率低。最优解使用Boyer-Moore投票算法，时间复杂度降为O(n)，空间复杂度O(1)。

🎯 代码技巧

• 利用多数元素超过一半的数学特性
• 采用抵消思想，相同+1，不同-1
• 无需实际统计次数，只需找到候选元素

4️⃣ 使用场景

✅ 适用情况：

• 需要找到出现次数超过一半的元素
• 数据流中查找多数元素
• 在线算法场景，需要实时处理

⚠️ 前提条件：

• 数组非空
• 保证存在多数元素（出现次数>n/2）

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n) - 只需遍历数组一次

• 💾 空间复杂度：O(1) - 只使用常数额外空间

6️⃣ 注意事项

🚩 边界情况：

• 数组只有一个元素
• 多数元素刚好出现⌊n/2⌋+1次
• 数组长度为偶数或奇数的情况

💥 易错点：

• 忘记处理计数器为0时的候选元素更新
• 混淆多数元素的判断条件（>n/2而非≥n/2）
• 在实际应用中未验证结果确实为多数元素

7️⃣ 补充说明

"战场对决"类比

/**
 * 多数元素查找 - Boyer-Moore投票算法详解
 * 
 * 核心思想：多数元素的数量超过总数的一半
 * 就像一支军队人数超过总兵力的50%，即使与其他所有军队一对一战斗，
 * 最后剩下的肯定还是这支军队的人
 */
int majorityElement(int* nums, int numsSize) {
    // 初始时，我们假设第一个士兵（数组第一个元素）是我们要找的军队
    int candidate = nums[0];  // 当前候选军队
    int count = 1;            // 当前军队的士兵数量（初始为1）
    
    // 从第二个士兵开始检阅整个军队
    for (int i = 1; i < numsSize; i++) {
        // 如果战场上没有士兵了（count为0）
        if (count == 0) {
            // 更换候选军队为当前遇到的士兵所属军队
            candidate = nums[i];  // 新的候选军队
            count = 1;            // 这支军队当前有1个士兵
        } 
        // 如果当前士兵属于我们正在追踪的候选军队
        else if (nums[i] == candidate) {
            count++;  // 该军队士兵数量+1
        } 
        // 如果当前士兵属于其他军队（敌对军队）
        else {
            count--;  // 我们候选军队的士兵与敌军士兵同归于尽，数量-1
        }
    }
    
    // 最终剩下的候选军队就是多数军队（多数元素）
    return candidate;
}

具体例子演示

以数组 [2,2,1,1,1,2,2] 为例：

步骤	当前元素	candidate	count	说明
初始	-	2	1	假设第一个元素2是多数元素
i=1	2	2	2	遇到相同元素，count++
i=2	1	2	1	遇到不同元素，count--（2和1抵消）
i=3	1	2	0	再次抵消，count变为0
i=4	1	1	1	count为0，更换候选元素为1
i=5	2	1	0	1和2抵消，count变为0
i=6	2	2	1	count为0，更换候选元素为2

加载评论中...