【每日算法】LeetCode 169. 多数元素:从暴力枚举到巧妙投票

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 169. 多数元素：从暴力枚举到巧妙投票

1. 题目描述

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

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

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

示例 1：
输入：nums = [3,2,3]
输出：3

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

2. 问题分析

1. 核心任务：找到一个在数组中占比超过一半的元素。由于该元素出现次数count > n/2，这意味着它是数组中最“主流”的那个。
2. 输入保证：题目假设数组非空且一定存在多数元素，这简化了我们的问题，我们不需要处理“不存在”的边界情况。
3. 前端关联思考：想象你正在分析用户行为日志数组（例如，点击最多的按钮ID），或者在处理一个由状态更新组成的流，你需要快速找出当前的主导状态。这类“寻找主元素”的问题在前端大数据处理、监控、降级策略中都有潜在应用。

3. 解题思路

此题有多种解法，其核心是如何高效地统计或识别出这个“众数”。

1. 哈希表计数法 (HashMap Count)：最直观的“前端思维”，类似用Map或对象统计频率。
2. 排序法 (Sorting)：利用多数元素超过一半的特性，排序后中间位置的元素一定是它。
3. 分治法 (Divide and Conquer)：将问题分解，在子数组中寻找众数，然后合并结果（本题中此法并非最优，但有助于理解分治思想）。
4. 摩尔投票法 (Boyer-Moore Voting Algorithm)：本题的最优解。核心思想是“对抗消耗”，因为多数元素的数量比其他所有元素加起来都多，所以像打仗一样，即使一对一同归于尽，最后剩下的也一定是多数元素。

最优解：摩尔投票法，因为它达到了O(n) 时间复杂度和O(1) 空间复杂度，无需额外空间且只需一次遍历。

4. 各思路代码实现

4.1 哈希表计数法

/** * 哈希表计数法 * 思路：遍历数组，用Map记录每个数字出现的次数，当某个数字的计数超过 n/2 时，返回它。 * 时间复杂度：O(n)，我们遍历了一次数组(n)和一次Map(最坏情况n)。 * 空间复杂度：O(n)，最坏情况下每个元素都不同，Map需要存储n个键值对。 */varmajorityElement=function(nums){// 创建哈希表（Map）用于计数constcountMap=newMap();// 多数元素的阈值，即出现次数需要大于这个值constmajorityThreshold=Math.floor(nums.length/2);for(letnumofnums){// 获取当前数字的计数，如果不存在则默认为0，然后加1constcurrentCount=(countMap.get(num)||0)+1;// 更新计数countMap.set(num,currentCount);// 判断：如果当前数字的计数已经超过阈值，立即返回// 得益于题目保证存在多数元素，我们可以提前返回if(currentCount>majorityThreshold){returnnum;}}// 根据题意，代码不会执行到这里。但为逻辑完整，可以返回null或-1。returnnull;};

4.2 排序法

/** * 排序法 * 思路：因为多数元素的个数超过一半，所以排序后，数组中间位置的元素一定是多数元素。 * 时间复杂度：O(n log n)，主要由排序算法决定（例如快排）。 * 空间复杂度：O(log n) ~ O(n)，取决于排序算法的空间开销（如快排的递归栈为O(log n))。 */varmajorityElement=function(nums){// 1. 对数组进行排序。JavaScript的sort()默认按字符串排序，需要传入比较函数进行数字排序。nums.sort((a,b)=>a-b);// 2. 返回位于数组中间位置的元素。// 例如: [1,2,2,2,3] (n=5) -> 中间索引为 2 -> nums[2] = 2// 例如: [2,2,1,1,1,2,2] (n=7) -> 中间索引为 3 -> nums[3] = 1 (？这里需要注意，原数组排序后为[1,1,1,2,2,2,2]，中间是nums[3]=2)// 实际上，对于长度n，中间索引是 Math.floor(n / 2)constmidIndex=Math.floor(nums.length/2);returnnums[midIndex];};

4.3 摩尔投票法（最优解）

/** * 摩尔投票法 (Boyer-Moore Majority Vote Algorithm) * 思路：核心是“正负抵消”。把多数元素记为+1，其他元素记为-1，由于多数元素数量占优，最终和一定为正。 * 我们遍历数组，维护一个“候选者”(candidate)和它的“生命值”(count)。 * 时间复杂度：O(n)，仅遍历一次数组。 * 空间复杂度：O(1)，只用了两个变量。 * 步骤分解说明： * 1. 初始化：候选者 candidate = null，票数 count = 0。 * 2. 遍历数组： * a. 如果 `count === 0`，说明当前没有候选者，或者前面的配对都抵消了。我们选择当前数字作为新的候选者。 * b. 如果当前数字 `num` 等于候选者 `candidate`，说明是“自己人”，票数加一 (count++)。 * c. 如果当前数字 `num` 不等于候选者 `candidate`，说明是“反对派”，票数减一 (count--)，相当于一票反对和一票支持抵消。 * 3. 遍历结束后，`candidate` 就是多数元素（根据题目保证）。 */varmajorityElement=function(nums){letcandidate=null;// 当前候选的多数元素letcount=0;// 候选元素的“净胜票数”for(letnumofnums){// 当票数为0时，前面的局面已经抵消，重新设定候选者if(count===0){candidate=num;}// 判断当前数字是否支持当前的候选者// 如果相等，票数增加；如果不相等，票数减少（抵消一票）count+=(num===candidate)?1:-1;}// 由于题目假设一定存在多数元素，所以candidate就是答案returncandidate;};// 附加验证步骤（如果题目不保证存在多数元素，则需要此步骤）varmajorityElementWithVerify=function(nums){letcandidate=null;letcount=0;// 第一遍遍历：找出候选者for(letnumofnums){if(count===0){candidate=num;}count+=(num===candidate)?1:-1;}// 第二遍遍历：验证候选者是否真的是多数元素count=0;for(letnumofnums){if(num===candidate){count++;}}// 判断出现次数是否超过一半if(count>Math.floor(nums.length/2)){returncandidate;}// 如果不是，根据题目要求返回特定值（本题不需要）returnnull;};

5. 各实现思路的复杂度、优缺点对比

6. 总结

6.1 通用解题模板与思路

对于“寻找多数元素/主元素”这类问题，可以遵循以下思考路径：

1. 暴力统计：首先想到哈希表，这是处理频率统计问题的“万金油”。
2. 利用特性优化空间：如果问题有特殊限制（如本题的“占比超过一半”），思考能否利用数学或逻辑特性减少空间使用。
   • 排序取中：当主元素占比超过一半时，中位数一定是它。
   • 摩尔投票法：是此类问题的经典最优解模板。其核心代码模板可以记忆：

     functionmajorityElement(nums){letcandidate,count=0;for(letnumofnums){if(count===0)candidate=num;count+=(num===candidate)?1:-1;}returncandidate;// 如果题目不保证，需要二次验证}

3. 分治思想：作为备选，用于练习“分而治之”的算法范式。

6.2 类似题目推荐

1. LeetCode 229. 求众数 II：寻找所有出现次数超过n/3的元素。这是摩尔投票法的进阶应用，需要维护两个候选者。
2. LeetCode 347. 前 K 个高频元素：哈希表计数 + 优先队列（或桶排序）的经典组合，前端可思考如何用Map和数组排序实现。
3. LeetCode 136. 只出现一次的数字：可以使用哈希表，但最优解是巧妙的位运算（异或），达到了 O(n) 时间和 O(1) 空间。
4. LeetCode 169. 多数元素本身在各种面试中频繁出现，是理解空间优化和摩尔投票法的入门必刷题。