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

Question

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

例如，如果 a = 4 , b = 6 和 n = 6 那么答案是 18因为列表是 4 6 8 12 16 18 20 24 28 30....

这是我使用的方法:

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

2. 生成 a 和 b 的倍数的列表(如上所示)直到small*n，因为要求的答案不能大于这个。

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

4. 将这个指针向后移动较大数字的倍数，直到 small*n(简单地通过 (small * n)/big 收回指针).

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

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

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

Answer 1

如前所述，找到 L=LCM(a,b)(此处为 12)
同时计算la = LCM/a, lb = LCM/b(这里是3,2)
请注意，L 位于行中的第 F = la + lb - 1 位置，而 LCM 的第 k 个倍数位于序列的第 k * F 位置(这里是k*4)
所以你可以很容易地找到:
-interval 其中第 n 个成员是:idx = n div F(这里 6 div 4 = 1 从 0 开始)
- 放置在这个区间内:p = div mod F(这里6 mod 4 = 2从0开始)

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