学习笔记|丑数系列算法-2

以下文章来源于labuladong ，作者labuladong

丑数 II

接下来提升难度，看下力扣第 264 题「丑数 II」，现在题目不是让你判断一个数是不是丑数，而是给你输入一个n，让你计算第n个丑数是多少，函数签名如下：

int nthUglyNumber(int n)

比如输入n = 10，函数应该返回 12，因为从小到大的丑数序列为1, 2, 3, 4, 5, 6, 8, 9, 10, 12，第 10 个丑数是 12（注意我们把 1 也算作一个丑数）。

这道题很精妙，你看着它好像是道数学题，实际上它却是一个合并多个有序链表的问题，同时用到了筛选素数的思路。

首先，我在前文 如何高效寻找质数 中也讲过高效筛选质数的「筛数法」：一个质数和除 1 以外的其他数字的乘积一定不是质数，把这些数字筛掉，剩下的就是质数。
基于筛数法的思路和丑数的定义，我们不难想到这样一个规律：如果一个数x是丑数，那么x * 2, x * 3, x * 5都一定是丑数。

如果我们把所有丑数想象成一个从小到大排序的链表，就是这个样子：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> ...

然后，我们可以把丑数分为三类：2 的倍数、3 的倍数、5 的倍数。这三类丑数就好像三条有序链表，如下：

能被 2 整除的丑数：

1*2 -> 2*2 -> 3*2 -> 4*2 -> 5*2 -> 6*2 -> 8*2 ->...

能被 3 整除的丑数：

1*3 -> 2*3 -> 3*3 -> 4*3 -> 5*3 -> 6*3 -> 8*3 ->...

能被 5 整除的丑数：

1*5 -> 2*5 -> 3*5 -> 4*5 -> 5*5 -> 6*5 -> 8*5 ->...

我们如果把这三条「有序链表」合并在一起并去重，得到的就是丑数的序列，其中第n个元素就是题目想要的答案：

1 -> 1*2 -> 1*3 -> 2*2 -> 1*5 -> 3*2 -> 4*2 ->...

所以这里就和 链表双指针技巧汇总 中讲到的合并两条有序链表的思路基本一样了，先看下合并有序链表的核心解法代码：

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点存储结果链表，p 指针指向结果链表
    ListNode dummy = new ListNode(-1), p = dummy;
    // p1, p2 分别在两条有序链表上
    ListNode p1 = l1, p2 = l2;
    
    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到结果链表
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }
    // 省略部分非核心代码...
}