169 - 多数元素

题目链接

169 - 多数元素

题目

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。使用时间复杂度为$O(n)$，空间复杂度为$O(1)$的方法。

思路

1. 数组排序：时间复杂度：$O(n\log n)$，空间复杂度：$O(1)$
2. 用哈希表计数：时间复杂度：$O(n)$，空间复杂度：$O(n)$
3. 随机数
4. 分治
5. Boyer Moore投票法

Boyer-Moore 多数投票算法是一种用于在数组中找到多数元素（即出现次数超过数组长度一半的元素）的高效算法。它分为两个主要阶段：候选阶段和验证阶段。

1. 候选阶段

在候选阶段，我们尝试找到一个可能的多数元素候选者。具体步骤如下：

• 初始化一个候选者 candidate 和一个计数器 count。开始时，candidate 为 null，count 为 0。
• 遍历数组中的每个元素：
  • 如果 count 为 0，说明当前没有候选者，将当前元素设为候选者，并将 count 设为 1。
  • 如果当前元素等于候选者，将 count 增加 1。
  • 如果当前元素不等于候选者，将 count 减少 1。

这个过程的直觉是：如果一个元素是多数元素，它最终会成为 candidate，因为它出现的次数超过了数组的一半。

2. 验证阶段

在验证阶段，我们需要确认候选者是否真的为多数元素。具体步骤如下：

• 初始化 count 为 0。
• 遍历数组，统计候选者 candidate 出现的次数。
• 如果 candidate 出现的次数超过数组长度的一半，返回 candidate。
• 否则，返回 null（尽管在保证多数元素存在的前提下，这一步不需要）。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = function (nums) {
  function boyerMoore() {
    let count = 0;
    let candidate = null;
    for (let num of nums) {
      if (count === 0) {
        candidate = num;
      }
      count += num === candidate ? 1 : -1;
    }
    return candidate;
  }

  const candidate = boyerMoore();
  const isMajority =
    nums.filter((num) => num === candidate).length >
    Math.floor(nums.length / 2);

  return candidate;
};