多数元素 (Majority Element)

数组哈希表投票算法

题目描述

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

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

通常题目会限制使用 O(1) 空间复杂度。

思路分析

最直观的策略是利用哈希表来记录频率。通过遍历整个数组，我们将每个遇到的数字作为键存入哈希表中，并实时累加其出现的次数。在每次更新计数值后，我们都会立即比对该数字的频率是否已经超过了数组长度的一半。由于题目明确保证多数元素必然存在，这种方法可以在满足条件的第一时间停止遍历并返回结果，其逻辑非常清晰且易于实现。

然而，如果我们需要在极端的内存限制下解决问题，Boyer-Moore 投票算法则展现了更加优雅的设计思想。该算法的核心是将多数元素与其他所有元素视为一种“对冲”关系：我们可以将多数元素看作正向的能量，而将所有其他非多数元素看作负向的抵消。由于多数元素的数量占据了数组的绝对优势（超过 50%），因此所有数字在相互抵消之后，最终存留下来的一定是那个多数元素。

在具体的执行过程中，我们维护一个候选人变量和一个计票器。每当我们遇到与当前候选人相同的数字时，计票器就会增加；而遇到不同的数字时，计票器则会减少，这本质上是让两个不同的数字“同归于尽”。当计票器归零时，意味着之前的候选人已经被完全抵消，此时我们只需将下一个遇到的数字设为新的候选人即可。这种奇妙的抵消机制确保了我们仅需 O(1) 的额外空间就能准确锁定目标。

示例代码

哈希表 (Map)

Boyer-Moore 投票算法 (推荐)

/**
 * 寻找数组中的多数元素（出现次数超过 n/2 的元素）
 * 使用哈希表 (Map) 记录频率
 * 时间复杂度: O(n) - 遍历一次数组
 * 空间复杂度: O(n) - 最坏环境下需要存储数组中所有不同的数
 * 
 * @param {number[]} nums 输入的数字数组
 * @returns {number | null} 返回多数元素，若数组为空则返回 null
 */
export function majorityElement(nums) {
  // 1. 基础校验：非数组或空数组返回 null
  if (!nums || !Array.isArray(nums) || nums.length === 0) {
    return null;
  }
  // 如果只有一个元素，直接返回该元素
  if (nums.length === 1) {
    return nums[0];
  }

  // 2. 初始化哈希表来记录每个数字出现的次数
  const hashMap = new Map();
  // 计算“多数”的标准（超过一半的长度）
  const threshold = nums.length / 2;

  // 3. 遍历数组进行计数
  for (const num of nums) {
    // 获取当前数字之前的次数，如果没有则默认为 0，然后加 1
    const count = (hashMap.get(num) || 0) + 1;
    
    // 实时检查：如果当前数字出现次数已经超过一半，直接返回
    if (count > threshold) {
      return num;
    }
    
    // 更新哈希表中的计数值
    hashMap.set(num, count);
  }
  
  return null;
}

/**
 * 寻找数组中的多数元素（出现次数超过 n/2 的元素）
 * 使用 Boyer-Moore 投票算法 (Moore Voting Algorithm)
 * 时间复杂度: O(n) - 只需遍历一次数组
 * 空间复杂度: O(1) - 只需要两个变量记录状态
 * 
 * @param {number[]} nums 输入的数字数组
 * @returns {number | null} 返回多数元素，若数组为空则返回 null
 */
export function majorityElement(nums) {
  // 基础校验：如果数组为空或未定义，直接返回 null
  if (!nums || !Array.isArray(nums) || nums.length === 0) {
    return null;
  }
  // 如果只有一个元素，直接返回该元素
  if (nums.length === 1) {
    return nums[0];
  }

  // 1. 初始化候选人 (candidate) 和计票器 (count)
  let count = 0;
  let candidate = null;

  // 2. 开始投票过程
  for (const num of nums) {
    // 如果计票器归零，说明之前的候选人被其他数字抵消了，
    // 我们选择当前的数字作为新的候选人。
    if (count === 0) {
      candidate = num;
    }

    // 计票规则：
    // 如果当前数字与候选人相同，计票加 1；
    // 如果不同，计票减 1（相当于两个不同的数字同归于尽）。
    count += candidate === num ? 1 : -1;
  }

  /**
   * 提示：根据 Boyer-Moore 算法原理，
   * 如果数组中一定存在出现次数超过 n/2 的元素，
   * 那么循环结束后 candidate 就是我们要找的答案。
   */
  return candidate;
}

复杂度分析

算法	时间复杂度	空间复杂度
哈希表	`O(n)`	`O(n)`
Boyer-Moore	`O(n)`	`O(1)`

示例演示 (Boyer-Moore)

以 nums = [2, 2, 1, 1, 1, 2, 2] 为例：

元素 (num)	候选人 (candidate)	计票 (count)	说明
2	2	1	初始 candidate = 2
2	2	2	相同，count++
1	2	1	不同，count--
1	2	0	不同，count--
1	1	1	count 为 0，candidate 更新为 1
2	1	0	不同，count--
2	2	1	count 为 0，candidate 更新为 2

最终胜出的候选人是 2。

#多数元素 (Majority Element)

#题目描述

#思路分析

#示例代码