枚举唯一的数字倍数

Question

假设我们给定一个正数数组

M

，比如说

[3, 5, 7]

，并且我们想要枚举所有数字，这些数字是其中任何一个的倍数，小于某个上限，比如说

K

，所以在这种情况下

0, 3, 5, 6, 7, 9, 10, 12, 14, 15...

。

当

M

的尺寸很大时，如何有效地做到这一点？

一种简单的方法是从 0 开始，对于每个值检查它是否除以

M

中的任何值，这不是很好，因为值可能很大，因此大多数数字不会被枚举，但会浪费计算。

我想以这样的方式枚举，使时间复杂度尽可能接近理论最小值，即。

O(Number of elements in sequence)

，这意味着是公倍数的值，例如

[2, 3]

序列中的 6 个，理想情况下不应比任何其他值需要更多的计算。

Answer 1

我认为你可以通过使用堆数据结构（下面的Python代码中的

PriorityQueue

queue

）来优化算法，以跟踪

M

列表中数字的下一个最小倍数，这些数字将被添加到枚举列表中，直到它达到

K

。堆数据结构的优势在于，它具有

O(1)

查找列表中最小值的查找时间，以及

O(log(n))

的插入和删除功能。

最初队列将包含

M

项目，每个项目具有以下结构

(<num 1>, <num 1>)

。

当最后一个枚举数小于

K

并且队列为空时，如果列表中不存在该值并且该值小于或等于

，我们可以不断拉取字典序最小的项目队列并将其追加到枚举列表中K

。然后，我们将一个新结构体追加到队列中，作为

(<num> + <multiple>, <multiple>)

来表示原始值的下一个倍数 (

<multiple>

)

估计的时间复杂度为

O(Klog(M))

，比原帖中的

O(KM)

更高效

from queue import PriorityQueue

M = [3, 5, 7]
K =19 

res = [0]

queue = PriorityQueue()

# Queue initialization
for m in M:
    queue.put((m, m)) # structure (<new value>, <its multiple>)

# continue looping while largest element in the result list is less than K: O(K)
while res[-1] < K and not(queue.empty()):
    # get the smallest element in the priority queue: O(log(n))
    val, multiple = queue.get()

    if res[-1] != val and val <= K:
        # value is not already in the result list, then append to the list
        res.append(val)
    
    if val + multiple <= K:
        # append new candidate value which is the next multiple of the original value: O(log(n))
        queue.put((val + multiple, multiple))

print(res)