满足O(N)时间O(1)空间的正整数数组元素频次判断问题

问题背景 #

给定长度为N的正整数数组，所有元素值远大于N（千倍及以上），需判断数组中是否存在元素出现次数超过指定阈值（示例中为超过4次），要求时间复杂度O(N)、空间复杂度O(1)。

示例数组：ARRAY[] = {1111, 2222, 3333, 2222, 3333, 3333, 3333, 1111, 2222, 3333}（N=10，目标：判断是否存在元素出现次数>4）

解决方案 #

可通过摩尔投票法筛选候选+二次遍历验证的方式实现，完全满足约束条件：

1. 筛选候选元素 #

遍历数组一次，维护两个变量：candidate（存储候选元素）和count（候选计数）：

• 初始状态：candidate = null，count = 0；
• 遍历每个元素num：
  • 若count == 0，将candidate设为当前num，count置1；
  • 若num == candidate，count += 1；
  • 否则，count -= 1。

对示例数组遍历后，candidate会锁定为3333——因为它的出现次数占比最高，会在投票过程中留存。

2. 验证候选元素的实际出现次数 #

再次遍历数组，统计candidate的出现次数：

• 若统计结果超过指定阈值（示例中为4次），则存在符合条件的元素；
• 反之则不存在。

示例中3333共出现6次，超过4次，因此判定存在。

方案合理性说明 #

• 时间复杂度：两次线性遍历，总耗时O(N)；
• 空间复杂度：仅使用固定数量的变量，空间开销O(1)；
• 适配元素大小约束：此方法无需修改原数组元素，也不需要将元素值作为索引使用，因此元素远大于N的条件不影响逻辑执行。

内容的提问来源于stack exchange，提问作者54Y4N