【LeetCode: 169. 多数元素 + Boyer-Moore 投票算法】

硕风和炜

于 2025-01-29 22:30:24 发布

阅读量732

点赞数 19

分类专栏： LeetCode每日一题打卡文章标签：算法 leetcode java 摩尔投票

本文链接：https://blog.csdn.net/coder_ljw/article/details/145394656

版权

LeetCode每日一题打卡专栏收录该内容

606 篇文章

订阅专栏

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

🚩 题目链接

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) 的算法解决此问题。

🌟 求解思路&实现代码&运行结果

⚡ Boyer-Moore 投票算法

🥦 求解思路

参考题解：Leetcode官方题解
摩尔投票法 (Boyer-Moore Voting Algorithm)：
- 核心思想：通过抵消不同的元素，最终剩下的候选者即为多数元素。
- 初始化：count 记录当前候选者的“票数”，candidate 记录当前候选者。
- 遍历数组：
  1. 如果 count == 0，说明当前候选者被完全抵消，将当前元素设为新的候选者。
  2. 如果当前元素等于候选者，count++；否则，count–。
  3. 返回结果：遍历结束后，candidate 即为多数元素。
有了基本的思路，接下来我们就来通过代码来实现一下。

🥦 实现代码

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;
    }
}