algorithm - 针对涉及计算 2 个或更多数字的唯一倍数的问题优化空间复杂度？

Question

样本输入：

14
3
4
8

我只需要找出最后 3 个数字的唯一倍数，直到第一个数字。因此，3、4 和 8 的唯一倍数直到 14，即 3、9、12、4、8。

我正在考虑的解决方案要么涉及多个数据结构，并且仅在末尾附加并计算结构的大小，要么涉及 O(N^2) 解决方案，该解决方案涉及在每次潜在插入时遍历结构避免重复。

降低这个问题复杂性的解决方案最终会比它需要的更复杂吗？

标签： algorithmdata-structures

Answer 1

您可以通过使用最小堆来解决O(n)空间和O(mlogn)时间复杂度（m即总倍数）。用你的起始数字填充堆，用它们当前的倍数（现在只是数字本身）作为它们的键。将变量设置为last_seen小于您的最小起始数字（可能为零）。

现在，从堆中删除 min 键，如果它大于last_seen和小于或等于您的target_value打印它。然后设置last_seen等于这个键。将键的值（表示当前倍数）增加它存储的起始数字的值（3 + 3 -> 6，6 + 3 -> 9等），然后将其重新添加到最小堆中。重复此过程，直到 min 键大于target_value。如果在任何时候 min 键等于last_seen，则该数字是重复的 - 只需跳过打印步骤并照常进行。