求解两数倍数有序列表的第n项（亚马逊招聘挑战真题）

我之前在亚马逊的招聘挑战里碰到过这个一模一样的问题，当时琢磨出了两种可行的思路，分享给你：

问题回顾 #

给定两个数a和b，将它们的所有倍数按升序排列成一个列表，找出列表中的第n个元素。例如当a=4、b=6、n=6时，答案为18，对应完整列表的前10项是：4 6 8 12 16 18 20 24 28 30……

思路一：生成合并列表（适合小n场景） #

这个思路比较直观，适合n不大的情况：

• 先把a和b中的较小值赋值给small，较大值赋值给big。这么做的核心原因是：第n个目标元素一定不会超过small * n（毕竟small自己的前n个倍数里，已经足够容纳穿插进来的big的倍数了）。
• 分别生成small在small * n范围内的所有倍数，以及big在同一范围内的所有倍数。
• 把两个列表合并、去重，再按升序排序，最后取第n-1个元素（因为列表索引从0开始）就是答案。

用题目中的例子验证：
small=4，small*n=24，4的倍数列表是[4,8,12,16,20,24]，6的倍数列表是[6,12,18,24]；合并去重排序后得到[4,6,8,12,16,18,20,24]，第6个元素（索引5）正好是18，完全符合要求。

思路二：双指针法（适合大n场景） #

如果n很大，生成完整列表会占用过多内存，这时候双指针法就更高效：

• 初始化两个指针i=1、j=1，分别指向a的第i个倍数（a*i）和b的第j个倍数（b*j）。
• 初始化计数器count=0，目标结果result=0。
• 循环执行以下步骤直到count == n：
  • 比较a*i和b*j的大小：
    • 如果a*i < b*j：把a*i设为当前结果，count +=1，i +=1。
    • 如果a*i > b*j：把b*j设为当前结果，count +=1，j +=1。
    • 如果两者相等：把这个值设为当前结果，count +=1，同时i +=1、j +=1（避免重复计数）。

还是用题目例子走一遍流程：

1. 41=4 vs 61=6 → 取4，count=1，i=2
2. 42=8 vs 61=6 → 取6，count=2，j=2
3. 42=8 vs 62=12 → 取8，count=3，i=3
4. 43=12 vs 62=12 → 取12，count=4，i=4、j=3
5. 44=16 vs 63=18 → 取16，count=5，i=5
6. 45=20 vs 63=18 → 取18，count=6 → 得到结果18，结束循环

这个方法的时间复杂度是O(n)，空间复杂度是O(1)，完全不需要额外存储大量倍数，处理大n的情况非常友好。

内容的提问来源于stack exchange，提问作者virmis_007