algorithm - 两个数的倍数列表的第 n 个数

几个月前在亚马逊招聘挑战中遇到了这个问题。
给定两个数字 a 和 b 以及它们升序的倍数列表，找到 n 的倍数。

例如，如果 a = 4 , b = 6 和 n = 6 那么答案是 18因为列表是 4 6 8 12 16 18 20 24 28 30....
这是我使用的方法:

选择 a 和 b 中较小的一个。分配给小。将另一个分配给大。

生成 a 和 b upto 的倍数列表(如上图)small*n ，因为所需的答案不能超过这个。

创建指向此列表中最后一个数字的指针。

将此指针移回较大数字的倍数，直到 small*n (只需通过 (small * n)/big 收回指针)。

将指针向前移动 a 和 b 的最小公倍数，直到 small * n 。这是必需的答案。

这种方法适用于小型测试用例，但适用于较大的测试用例。

请提出一种时间复杂度较低的方法。出于某种原因，Mathjax 无法在我的任何浏览器中运行。

最佳答案

注意到，找到 L=LCM(a,b) (here 12)
还要计算la = LCM/a, lb = LCM/b(这里是3,2)
请注意，L 代表行中的第 F = la + lb - 1 -th 个位置，而 LCM 的第 k 个倍数代表序列的第 k * F -th 个位置(此处为 k*4)
因此，您可以轻松找到:
-第n个成员的间隔:idx = n div F(这里6 div 4 = 1从0开始)
-放置在这个区间:p = div mod F(这里6 mod 4 = 2从0开始)

现在您必须在 0..LCM - 1 范围内找到第 p 个项目。请注意，您不需要构建列表(可能的方法 - 二分搜索)

关于algorithm - 两个数的倍数列表的第 n 个数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49484305/