algorithm - 给定一个数字 K 和一组已排序的数字。查找集合中是否有任何数字可以除

Question

给定一个数字 k 和一组已排序的数字。查找集合中是否有任何数字可以除此数字。

例如，如果 k = 8，并且集合是 {3,4,5}，4 将除以 8。4 就是答案。

最坏情况的解决方案是 O(n)。

我们能做得更好吗？

Answer 1

如何分解数字（8 给我们 4 2 1）然后搜索给定集合中的因子？您可以使用设置交集或二等分搜索您的因素列表。我认为它会给你一个更大的集合更快的答案。

Answer 2

如果 k 是素数，则它在集合中没有因子，你就完成了。否则，k = p*q 其中 p 是 k 的最小因子。对 q 进行二分搜索。如果找到，你就完成了。否则，重构 k=p'*q'，其中 p' 是 p 之后 k 的下一个最大因子——如果没有，你就完成了。否则，继续对 q' 进行二分搜索——注意 q' < q，因此您可以使用用于 q 的上限继续搜索。继续直到找到一个因子或者您已经搜索了 k 的最大因子。这是 O(logn)。在 k = 8 的具体情况下，您将首先搜索 4，然后搜索 2 ...如果两者都没有找到，则该集合不包含 k 的除数。

编辑：嗯......我想这不是 O(logn)。例如，如果列表包含 k 的每个因子 f 的 f-1，那么您将不得不连续搜索每个 f，每次都点击 f-1 ... 那将是 O(n)。

Answer 3

计算 k 的 gcd 和集合成员的乘积。例如，gcd(3*4*5,8) = 4。