当数组M规模较大时，高效枚举其元素的唯一倍数（小于上限K）

给定正整数数组M，要枚举所有小于K的、属于M中任意元素的倍数的数（比如M=[3,5,7]时，结果包含0,3,5,6,7,9,...），朴素的逐个检查法效率极低——当K很大时，绝大多数数都不是目标数，会浪费大量计算资源。我们需要一种时间复杂度接近**O(N)**的方法（N是最终序列的元素个数），同时避免重复处理公倍数（比如[2,3]中的6，开销不能高于其他数）。

核心解法：最小堆+哈希去重 #

这种方法直接生成目标倍数，通过堆保证每次取出当前最小的倍数，用哈希集合避免重复加入公倍数，整体效率接近理论最优。

步骤说明

1. 预处理数组：

   • 去重：重复元素会导致重复生成倍数，先过滤掉M中的重复值。
   • 过滤无效元素：移除大于等于K的元素（它们的最小倍数就是自身，已经超出上限），同时确保元素是正整数。

2. 初始化数据结构：

   • 最小堆：存储元组(当前倍数, 对应原数)，用于每次取出最小的待处理倍数。
   • 哈希集合：记录已经加入过堆的数，避免重复加入公倍数（比如6会被2和3同时生成，只需要处理一次）。
   • 结果列表：先加入0（0是所有正整数的倍数）。

3. 生成目标序列：

   • 循环从堆中取出最小的(current, m)：
     • 如果current >= K，终止循环。
     • 将current加入结果列表。
     • 计算下一个倍数current + m，如果这个数不在哈希集合中，就加入堆和集合。

代码示例（Python）

def enumerate_multiples(M, K):
    if K <= 0:
        return []
    
    # 预处理：去重+过滤无效元素
    unique_M = list({m for m in M if m > 0 and m < K})
    result = [0] if 0 < K else []
    
    if not unique_M:
        return result
    
    import heapq
    heap = []
    seen = set()
    
    # 初始化堆
    for m in unique_M:
        heapq.heappush(heap, (m, m))
        seen.add(m)
    
    while heap:
        current, m = heapq.heappop(heap)
        if current >= K:
            break
        result.append(current)
        next_multiple = current + m
        if next_multiple not in seen:
            seen.add(next_multiple)
            heapq.heappush(heap, (next_multiple, m))
    
    return result

# 测试示例
print(enumerate_multiples([3,5,7], 16))
# 输出：[0, 3, 5, 6, 7, 9, 10, 12, 14, 15]

复杂度分析

• 时间复杂度：每个目标数只会被加入堆一次、取出一次，堆操作的时间是O(log |M|)（|M|是预处理后数组的大小）。总时间为O(|M| + N log |M|)，当N远大于|M|时，接近O(N)，满足要求。
• 空间复杂度：堆的大小最多为|M|，哈希集合存储所有已处理的倍数，空间为O(N)。

边界情况处理 #

• 当K=1：直接返回[0]，这是唯一小于1的倍数。
• 当M包含1：所有小于K的数都是倍数，可直接生成range(0, K)，比堆方法更高效。
• 当M为空或所有元素都大于等于K：仅返回[0]（如果K>0）。

替代方案：归并有序序列 #

把每个元素的倍数看作一个有序序列（比如3的序列是3,6,9,...），然后用归并排序的思路合并这些序列，同时去重。这种方法的复杂度和堆方法一致，但实现起来需要跟踪每个序列的当前位置，代码量稍大，适合没有优先队列库的场景。

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