给定一个数字 K 和一组已排序的数字。查找集合中是否有任何数字可以整除
给定一个数字 k 和一组已排序的数字。查找集合中是否有任何数字可以整除该数字。
例如，如果 k = 8，且集合为 { 3, 4, 5}，则 4 将除以 8。4 就是答案。
最坏情况的解决方案是 O(n)。
我们能做得更好吗？
Given a number k and a set of sorted numbers. Find if there is any number in the set which divides this number.
For example if k = 8, and set is { 3, 4, 5}, 4 will divide 8. 4 is the answer.
Worst case solution is O(n).
Can we do it better?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
将数字因式分解（8 给出 4 2 1）然后在给定的集合中搜索因式怎么样？您可以使用设置交集或二分法搜索因子列表。我认为它会给你一个对于大集合更快的答案。
How about factorize the number (8 gives us 4 2 1) then search for the factors in your given set? You can use set intersections or bisection search your list of factors. I think it will give you a quicker answer for large sets.
如果 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)。
If k is prime, it has no factors in the set and you're done. Otherwise, k = p*q where p is k's smallest factor. Do a binary search for q. If found, you're done. Otherwise, refactor k=p'*q', where p' is the next largest factor of k after p -- if none, you're done. Otherwise, continue the binary search for q' -- note that q' < q, so you can continue the search with the high bound used for q. Continue until a factor is found or you've searched for k's largest factor. This is O(logn). In the concrete case of k = 8, you would search first for 4, then for 2 ... if neither is found then the set does not contain a divisor of k.
EDIT:
Hmmm ... I guess this isn't O(logn). If, e.g., the list contained f-1 for every factor f of k, then you would have to search for each f in succession, hitting f-1 each time ... that would be O(n).
计算 k 的 gcd 与集合成员的乘积。例如，gcd(3*4*5,8) = 4。
Calculate the gcd of k and the product of the members of the set. For the example, gcd(3*4*5,8) = 4.