Boyer-Moore 多数投票算法

功能说明

majorityElement 使用 Boyer-Moore 投票算法在一次遍历中寻找出现次数超过一半的元素，第二遍只做计数确认，因此不会把普通候选误报为多数。majorityElements 将同一思路扩展为 Misra-Gries 摘要，可一次找出所有超过给定阈值的值。适合投票统计、日志热点识别、异常来源定位等场景。

关键代码

主函数维护候选值与余额：余额归零时更换候选，遇到相同值加一，遇到不同值减一。由于多数元素数量超过其余元素总和，最终候选必然是它，但必须第二次计数确认。扩展版本按阈值计算槽位数，槽满后用递减计数器抵消新值，最后再统计候选的真实频次并按阈值过滤。

使用注意

算法只在存在严格多数时保证正确；对普通数据第二遍确认会返回 null，这是预期行为。比较使用严格相等，对象需要按引用比较，若要按字段统计应先映射为主键。阈值越小需要的槽位越多，空间是 O(1/threshold)。输入数组不会被修改，但扩展版本返回顺序取决于 Map 插入顺序，不应依赖。

验证方式

测试空数组、单元素、无多数与恰好一半的边界，确保返回 null。构造包含多数元素的数组并断言结果正确，同时验证对象引用场景。对扩展版本生成三组高频值，确认阈值过滤准确；再测试非法阈值、阈值等于 1 以及所有元素相同的情况。最后用大数组对比朴素计数结果，验证一致性与线性复杂度。

代码示例

// Boyer-Moore majority vote: O(n) time, O(1) space.
export function majorityElement(values) {
  if (!Array.isArray(values) || values.length === 0) return null;
  let candidate = null;
  let balance = 0;
  for (const value of values) {
    if (balance === 0) {
      candidate = value;
      balance = 1;
    } else if (value === candidate) {
      balance += 1;
    } else {
      balance -= 1;
    }
  }
  let occurrences = 0;
  for (const value of values) {
    if (value === candidate) occurrences += 1;
  }
  return occurrences > values.length / 2 ? candidate : null;
}

export function majorityElements(values, threshold = 0.5) {
  if (!(threshold > 0 && threshold <= 1)) {
    throw new RangeError("threshold must be in (0, 1]");
  }
  const slots = Math.max(1, Math.ceil(1 / threshold) - 1);
  const counters = new Map();
  for (const value of values) {
    if (counters.has(value)) {
      counters.set(value, counters.get(value) + 1);
    } else if (counters.size < slots) {
      counters.set(value, 1);
    } else {
      for (const [key, count] of counters) {
        if (count === 1) counters.delete(key);
        else counters.set(key, count - 1);
      }
    }
  }
  const totals = new Map();
  for (const value of values) {
    if (counters.has(value)) totals.set(value, (totals.get(value) ?? 0) + 1);
  }
  return [...totals]
    .filter(([, count]) => count > values.length * threshold)
    .map(([value]) => value);
}