一文秒杀所有丑数系列问题

labuladong原创双指针数学约 6261 字

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
1201. Ugly Number III	1201. 丑数 III	🟠
263. Ugly Number	263. 丑数	🟢
264. Ugly Number II	264. 丑数 II	🟠
313. Super Ugly Number	313. 超级丑数	🟠
-	剑指 Offer 49. 丑数	🟠

前置知识

阅读本文前，你需要先学习：

最近读者群里有个读者跟我私信，说去面试微软遇到了一系列和数学相关的算法题，直接懵圈了。我看了下题目发现这些题其实就是 LeetCode 上面「丑数」系列问题的修改版。

首先，「丑数」系列问题属于会者不难难者不会的类型，因为会用到些数学定理嘛，如果没有专门学过，靠自己恐怕是想不出来的。

另外，这类问题而且非常考察抽象联想能力，因为它不仅仅要用到数学定理，还需要你把题目抽象成链表相关的题目运用双指针技巧，或者抽象成数组相关的题目运用二分搜索技巧。

那么今天我就来用一篇文章把所有丑数相关的问题一网打尽，看看这类问题能够如何变化，应该如何解决。

丑数 I

首先是力扣第 263 题「丑数」，题目给你输入一个数字 n，请你判断 n 是否为「丑数」。所谓「丑数」，就是只包含质因数 2、3 和 5 的正整数。

函数签名如下：

boolean isUgly(int n)

比如 12 = 2 x 2 x 3 就是一个丑数，而 42 = 2 x 3 x 7 就不是一个丑数。

这道题其实非常简单，前提是你知道算术基本定理（正整数唯一分解定理）：

任意一个大于 1 的自然数，要么它本身就是质数，要么它可以分解为若干质数的乘积。

既然任意一个大于一的正整数都可以分解成若干质数的乘积，那么丑数也可以被分解成若干质数的乘积，且这些质数只能是 2, 3 或 5。

有了这个思路，就可以实现 isUgly 函数了：

java 🟢

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        // 如果 n 是丑数，分解因子应该只有 2, 3, 5
        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;
        // 如果能够成功分解，说明是丑数
        return n == 1;
    }
}

cpp 🤖

class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) return false;
        // 如果 n 是丑数，分解因子应该只有 2, 3, 5
        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;
        // 如果能够成功分解，说明是丑数
        return n == 1;
    }
};

python 🤖

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        # 如果 n 是丑数，分解因子应该只有 2, 3, 5
        while n % 2 == 0:
            n //= 2
        while n % 3 == 0:
            n //= 3
        while n % 5 == 0:
            n //= 5
        # 如果能够成功分解，说明是丑数
        return n == 1

go 🤖

func isUgly(n int) bool {
    if n <= 0 {
        return false
    }
    // 如果 n 是丑数，分解因子应该只有 2, 3, 5
    for n % 2 == 0 {
        n /= 2
    }
    for n % 3 == 0 {
        n /= 3
    }
    for n % 5 == 0 {
        n /= 5
    }
    // 如果能够成功分解，说明是丑数
    return n == 1
}

javascript 🤖

var isUgly = function(n) {
  if (n <= 0) return false;
  // 如果 n 是丑数，分解因子应该只有 2, 3, 5
  while (n % 2 == 0) n /= 2;
  while (n % 3 == 0) n /= 3;
  while (n % 5 == 0) n /= 5;
  // 如果能够成功分解，说明是丑数
  return n == 1;
};

丑数 II

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

java 🟢

int nthUglyNumber(int n)

cpp 🤖

int nthUglyNumber(int n)

python 🤖

def nthUglyNumber(n: int) -> int:

go 🤖

func nthUglyNumber(n int) int {}

javascript 🤖

var nthUglyNumber = function(n) {}

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

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

首先，我在前文如何高效寻找质数中也讲过高效筛选质数的「筛数法」：一个质数和除 1 以外的其他数字的乘积一定不是质数，把这些数字筛掉，剩下的就是质数。

Wikipedia 的这幅图很形象：

基于筛数法筛选质数的思路和丑数的定义，我们不难想到这样一个规律：如果一个数 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 ->...

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

java 🟢

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;
    }
    // 省略部分非核心代码...
}

cpp 🤖

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 虚拟头结点存储结果链表，p 指针指向结果链表
    ListNode* dummy = new ListNode(-1), *p = dummy;
    
    // p1, p2 分别在两条有序链表上
    ListNode* p1 = l1, *p2 = l2;

    while (p1 != nullptr && p2 != nullptr) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到结果链表
        if (p1->val > p2->val) {
            p->next = p2;
            p2 = p2->next;
        } else {
            p->next = p1;
            p1 = p1->next;
        }
        // p 指针不断前进
        p = p->next;
    }
    // 省略部分非核心代码...
}

python 🤖

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

go 🤖

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    // 虚拟头结点存储结果链表，p 指针指向结果链表
    var dummy = &ListNode{-1, nil}, p = dummy
    
    // p1, p2 分别在两条有序链表上
    var p1 = l1
    var p2 = l2

    for p1 != nil && p2 != nil {
        // 比较 p1 和 p2 两个指针
        if p1.Val > p2.Val {
            p.Next = p2
            p2 = p2.Next
        } else {
            p.Next = p1
            p1 = p1.Next
        }
        // 将值较小的的节点接到结果链表
        p = p.Next
    }
    
    // p 指针不断前进

    // 省略部分非核心代码...
}

javascript 🤖

function mergeTwoLists(l1, l2) {
    // 虚拟头结点存储结果链表，p 指针指向结果链表
    var dummy = new ListNode(-1), p = dummy;
    // p1, p2 分别在两条有序链表上
    var 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;
    }
    // 省略部分非核心代码...
}

对于这道题，我们抽象出三条有序的丑数链表，合并这三条有序链表得到的结果就是丑数序列，其中第 n 个丑数就是题目想要的答案。

类比合并两个有序链表，看下这道题的解法代码：

java 🟢

class Solution {
    public int nthUglyNumber(int n) {
        // 可以理解为三个指向有序链表头结点的指针
        int p2 = 1, p3 = 1, p5 = 1;
        // 可以理解为三个有序链表的头节点的值
        int product2 = 1, product3 = 1, product5 = 1;
        // 可以理解为最终合并的有序链表（结果链表）
        int[] ugly = new int[n + 1];
        // 可以理解为结果链表上的指针
        int p = 1;

        // 开始合并三个有序链表，找到第 n 个丑数时结束
        while (p <= n) {
            // 取三个链表的最小结点
            int min = Math.min(Math.min(product2, product3), product5);
            // 将最小节点接到结果链表上
            ugly[p] = min;
            p++;
            // 前进对应有序链表上的指针
            if (min == product2) {
                product2 = 2 * ugly[p2];
                p2++;
            }
            if (min == product3) {
                product3 = 3 * ugly[p3];
                p3++;
            }
            if (min == product5) {
                product5 = 5 * ugly[p5];
                p5++;
            }
        }
        // 返回第 n 个丑数
        return ugly[n];
    }
}

cpp 🤖

class Solution {
public:
    int nthUglyNumber(int n) {
        // 可以理解为三个指向有序链表头结点的指针
        int p2 = 1, p3 = 1, p5 = 1;
        // 可以理解为三个有序链表的头节点的值
        int product2 = 1, product3 = 1, product5 = 1;
        // 可以理解为最终合并的有序链表（结果链表）
        vector<int> ugly(n + 1);
        // 可以理解为结果链表上的指针
        int p = 1;

        // 开始合并三个有序链表，找到第 n 个丑数时结束
        while (p <= n) {
            // 取三个链表的最小结点
            int min_val = min({product2, product3, product5});
            // 将最小节点接到结果链表上
            ugly[p] = min_val;
            p++;
            // 前进对应有序链表上的指针
            if (min_val == product2) {
                product2 = 2 * ugly[p2];
                p2++;
            }
            if (min_val == product3) {
                product3 = 3 * ugly[p3];
                p3++;
            }
            if (min_val == product5) {
                product5 = 5 * ugly[p5];
                p5++;
            }
        }
        // 返回第 n 个丑数
        return ugly[n];
    }
};

python 🤖

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # 理解为三个指向有序链表头结点的指针
        p2, p3, p5 = 1, 1, 1
        # 理解为三个有序链表的头节点的值
        product2, product3, product5 = 1, 1, 1
        # 理解为最终合并的有序链表（结果链表）
        ugly = [0] * (n + 1)
        # 理解为结果链表上的指针
        p = 1

        # 开始合并三个有序链表，找到第 n 个丑数时结束
        while p <= n:
            # 取三个链表的最小结点
            min_val = min(product2, product3, product5)
            # 将最小节点接到结果链表上
            ugly[p] = min_val
            p += 1
            # 前进对应有序链表上的指针
            if min_val == product2:
                product2 = 2 * ugly[p2]
                p2 += 1
            if min_val == product3:
                product3 = 3 * ugly[p3]
                p3 += 1
            if min_val == product5:
                product5 = 5 * ugly[p5]
                p5 += 1
                
        # 返回第 n 个丑数
        return ugly[n]

go 🤖

func nthUglyNumber(n int) int {
    // 可以理解为三个指向有序链表头节点的指针
    p2, p3, p5 := 1, 1, 1
    // 可以理解为三个有序链表头节点的值
    product2, product3, product5 := 1, 1, 1
    // 可以理解为最终合并的有序链表（结果链表）
    ugly := make([]int, n+1)
    // 可以理解为结果链表上的指针
    p := 1

    // 开始合并三个有序链表，找到第 n 个丑数时结束
    for p <= n {
        // 取三个链表的最小结点
        min := min(min(product2, product3), product5)
        // 将最小节点接到结果链表上
        ugly[p] = min
        p++
        // 前进对应有序链表上的指针
        if min == product2 {
            product2 = 2 * ugly[p2]
            p2++
        }
        if min == product3 {
            product3 = 3 * ugly[p3]
            p3++
        }
        if min == product5 {
            product5 = 5 * ugly[p5]
            p5++
        }
    }

    // 返回第 n 个丑数
    return ugly[n]
}

func min(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

javascript 🤖

var nthUglyNumber = function(n) {
    // 可以理解为三个指向有序链表头结点的指针
    let p2 = 1, p3 = 1, p5 = 1;
    // 可以理解为三个有序链表的头节点的值
    let product2 = 1, product3 = 1, product5 = 1;
    // 可以理解为最终合并的有序链表（结果链表）
    let ugly = new Array(n + 1);
    // 可以理解为结果链表上的指针
    let p = 1;

    // 开始合并三个有序链表，找到第 n 个丑数时结束
    while (p <= n) {
        // 取三个链表的最小结点
        let min = Math.min(Math.min(product2, product3), product5);
        // 将最小节点接到结果链表上
        ugly[p] = min;
        p++;
        // 前进对应有序链表上的指针
        if (min == product2) {
            product2 = 2 * ugly[p2];
            p2++;
        }
        if (min == product3) {
            product3 = 3 * ugly[p3];
            p3++;
        }
        if (min == product5) {
            product5 = 5 * ugly[p5];
            p5++;
        }
    }

    // 返回第 n 个丑数
    return ugly[n];
};

我们用 p2, p3, p5 分别代表三条丑数链表上的指针，用 product2, product3, product5 代表丑数链表上节点的值，用 ugly 数组记录有序链表合并之后的结果。

有了之前的铺垫和类比，你应该很容易看懂这道题的思路了，接下来我们再提高一点难度。

超级丑数

看下力扣第 313 题「超级丑数」，这道题给你输入一个质数列表 primes 和一个正整数 n，请你计算第 n 个「超级丑数」。所谓超级丑数是一个所有质因数都出现在 primes 中的正整数，函数签名如下：

java 🟢

int nthSuperUglyNumber(int n, int[] primes)

cpp 🤖

int nthSuperUglyNumber(int n, int* primes)

python 🤖

def nthSuperUglyNumber(n: int, primes: List[int]) -> int:

go 🤖

func nthSuperUglyNumber(n int, primes []int) int {}

javascript 🤖

var nthSuperUglyNumber = function(n, primes) {}

如果让 primes = [2, 3, 5] 就是上道题，所以这道题是上道题的进阶版。

不过思路还是类似的，你还是把每个质因子看做一条有序链表，上道题相当于让你合并三条有序链表，而这道题相当于让你合并 len(primes) 条有序链表，也就是双指针技巧秒杀七道链表题目中讲过的「合并 K 条有序链表」的思路。

注意我们在上道题抽象出了三条链表，需要 p2, p3, p5 作为三条有序链表上的指针，同时需要 product2, product3, product5 记录指针所指节点的值，每次循环用 min 函数计算最小头结点。

这道题相当于输入了 len(primes) 条有序链表，我们不能用 min 函数计算最小头结点了，而是要用优先级队列来计算最小头结点，同时依然要维护链表指针、指针所指节点的值，我们可以用一个三元组来保存这些信息。

你结合双指针技巧秒杀七道链表题目合并 K 条有序链表的思路就能理解这道题的解法：

java 🟢

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        // 优先队列中装三元组 long[] {product, prime, pi}
        // 其中 product 代表链表节点的值，prime 是计算下一个节点所需的质数因子，pi 代表链表上的指针
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> {
            // 优先级队列按照节点的值排序
            return (int)(a[0] - b[0]);
        });

        // 把多条链表的头结点加入优先级队列
        for (int i = 0; i < primes.length; i++) {
            pq.offer(new long[]{ 1, primes[i], 1 });
        }

        // 可以理解为最终合并的有序链表（结果链表）
        long[] ugly = new long[n + 1];
        // 可以理解为结果链表上的指针
        int p = 1;

        while (p <= n) {
            // 取三个链表的最小结点
            long[] pair = pq.poll();
            long product = pair[0];
            long prime = pair[1];
            int index = (int)pair[2];

            // 避免结果链表出现重复元素
            if (product != ugly[p - 1]) {
                // 接到结果链表上
                ugly[p] = product;
                p++;
            }

            // 生成下一个节点加入优先级队列
            long[] nextPair = new long[]{ugly[index] * prime, prime, index + 1};
            pq.offer(nextPair);
        }
        return (int)ugly[n];
    }
}

cpp 🤖

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        // 优先队列中装三元组 {product, prime, pi}
        // 其中 product 代表链表节点的值，prime 是计算下一个节点所需的质数因子，pi 代表链表上的指针
        priority_queue<vector<long>, vector<vector<long>>, greater<vector<long>>> pq;
        for (int i = 0; i < primes.size(); i++) {
            pq.push({1, primes[i], 1});
        }

        // 可以理解为最终合并的有序链表（结果链表）
        vector<long> ugly(n + 1);
        // 可以理解为结果链表上的指针
        int p = 1;

        while (p <= n) {
            // 取三个链表的最小结点
            vector<long> pair = pq.top();
            pq.pop();
            long product = pair[0];
            long prime = pair[1];
            int index = pair[2];

            // 避免结果链表出现重复元素
            if (product != ugly[p - 1]) {
                // 接到结果链表上
                ugly[p] = product;
                p++;
            }

            // 生成下一个节点加入优先级队列
            pq.push({ugly[index] * prime, prime, index + 1});
        }
        return ugly[n];
    }
};

python 🤖

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        # 优先队列中装三元组 {product, prime, pi}
        # 其中 product 代表链表节点的值，prime 是计算下一个节点所需的质数因子，pi 代表链表上的指针
        pq = []
        for prime in primes:
            heapq.heappush(pq, [1, prime, 1])

        # 可以理解为最终合并的有序链表（结果链表）
        ugly = [0] * (n + 1)
        # 可以理解为结果链表上的指针
        p = 1

        while p <= n:
            # 取三个链表的最小结点
            product, prime, index = heapq.heappop(pq)
            # 避免结果链表出现重复元素
            if product != ugly[p - 1]:
                # 接到结果链表上
                ugly[p] = product
                p += 1

            # 生成下一个节点加入优先级队列
            heapq.heappush(pq, [ugly[index] * prime, prime, index + 1])
        return ugly[n]

go 🤖

func nthSuperUglyNumber(n int, primes []int) int {
    // 优先队列中装三元组 {product, prime, pi}
    // 其中 product 代表链表节点的值，prime 是计算下一个节点所需的质数因子，pi 代表链表上的指针
    pq := make(PriorityQueue, 0)
    for i := 0; i < len(primes); i++ {
        heap.Push(&pq, []int64{1, int64(primes[i]), 1})
    }

    // 可以理解为最终合并的有序链表（结果链表）
    ugly := make([]int64, n+1)
    // 可以理解为结果链表上的指针
    p := 1

    for p <= n {
        // 取三个链表的最小结点
        pair := heap.Pop(&pq).([]int64)
        product := pair[0]
        prime := pair[1]
        index := pair[2]

        // 避免结果链表出现重复元素
        if product != ugly[p-1] {
            // 接到结果链表上
            ugly[p] = product
            p++
        }

        // 生成下一个节点加入优先级队列
        heap.Push(&pq, []int64{ugly[index] * prime, prime, index + 1})
    }
    return int(ugly[n])
}

type PriorityQueue [][]int64

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i][0] < pq[j][0]
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.([]int64))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0 : n-1]
    return x
}

javascript 🤖

var nthSuperUglyNumber = function(n, primes) {
    // 优先队列中装三元组 {product, prime, pi}
    // 其中 product 代表链表节点的值，prime 是计算下一个节点所需的质数因子，pi 代表链表上的指针
    let pq = new MinPriorityQueue({ priority: (pair) => pair[0] });
    for (let prime of primes) {
        pq.enqueue([1, prime, 1]);
    }

    // 可以理解为最终合并的有序链表（结果链表）
    let ugly = new Array(n + 1);
    // 可以理解为结果链表上的指针
    let p = 1;

    while (p <= n) {
        // 取三个链表的最小结点
        let pair = pq.dequeue().element;
        let product = pair[0];
        let prime = pair[1];
        let index = pair[2];

        // 避免结果链表出现重复元素
        if (product != ugly[p - 1]) {
            // 接到结果链表上
            ugly[p] = product;
            p++;
        }

        // 生成下一个节点加入优先级队列
        pq.enqueue([ugly[index] * prime, prime, index + 1]);
    }
    return ugly[n];
};

防止 int 溢出

对于 Java/C++/Go 这种强类型语言，需要注意 int 类型可能会溢出。

虽然题目说第 n 个超级丑数不会超过 int 的上界 2^31 - 1，但是在计算 ugly[index] * prime 的时候还是会溢出的，所以需要用 long 或 int64 类型来存储三元组。

接下来看下第四道丑数题目，也是今天的压轴题。

丑数 III

这是力扣第 1201 题「丑数 III」，看下题目：

给你四个整数：n, a, b, c，请你设计一个算法来找出第 n 个丑数。其中丑数是可以被 a 或 b 或 c 整除的正整数。

这道题和之前题目的不同之处在于它改变了「丑数」的定义，只要一个正整数 x 存在 a, b, c 中的任何一个因子，那么 x 就是丑数。

比如输入 n = 7, a = 3, b = 4, c = 5，那么算法输出 10，因为符合条件的丑数序列为 3, 4, 5, 6, 8, 9, 10, ...，其中第 7 个数字是 10。

有了之前几道题的铺垫，你肯定可以想到把 a, b, c 的倍数抽象成三条有序链表：

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

然后将这三条链表合并成一条有序链表并去除重复元素，这样合并后的链表元素就是丑数序列，我们从中找到第 n 个元素即可：

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

有了这个思路，可以直接写出代码：

java 🟢

class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        // 可以理解为三个有序链表的头结点的值
        // 由于数据规模较大，用 long 类型
        long productA = a, productB = b, productC = c;
        // 可以理解为合并之后的有序链表上的指针
        int p = 1;

        long min = -666;

        // 开始合并三个有序链表，获取第 n 个节点的值
        while (p <= n) {
            // 取三个链表的最小结点
            min = Math.min(Math.min(productA, productB), productC);
            p++;
            // 前进最小结点对应链表的指针
            if (min == productA) {
                productA += a;
            }
            if (min == productB) {
                productB += b;
            }
            if (min == productC) {
                productC += c;
            }
        }
        return (int) min;
    }
}

cpp 🤖

class Solution {
public:
    int nthUglyNumber(int n, int a, int b, int c) {
        // 可以理解为三个有序链表的头结点的值
        // 由于数据规模较大，用 long 类型
        long productA = a, productB = b, productC = c;
        // 可以理解为合并之后的有序链表上的指针
        int p = 1;

        long minProduct = -666;

        // 开始合并三个有序链表，获取第 n 个节点的值
        while (p <= n) {
            // 取三个链表的最小结点
            minProduct = min({productA, productB, productC});
            p++;
            // 前进最小结点对应链表的指针
            if (minProduct == productA) {
                productA += a;
            }
            if (minProduct == productB) {
                productB += b;
            }
            if (minProduct == productC) {
                productC += c;
            }
        }
        return (int) minProduct;
    }
};

python 🤖

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        # 可以理解为三个有序链表的头结点的值
        productA, productB, productC = a, b, c
        # 可以理解为合并之后的有序链表上的指针
        p = 1

        min_product = -666

        # 开始合并三个有序链表，获取第 n 个节点的值
        while p <= n:
            # 取三个链表的最小结点
            min_product = min(productA, productB, productC)
            p += 1
            # 前进最小结点对应链表的指针
            if min_product == productA:
                productA += a
            if min_product == productB:
                productB += b
            if min_product == productC:
                productC += c
        return min_product

go 🤖

func nthUglyNumber(n int, a int, b int, c int) int {
    // 可以理解为三个有序链表的头结点的值
    productA, productB, productC := a, b, c
    // 可以理解为合并之后的有序链表上的指针
    p := 1

    minProduct := -666

    // 开始合并三个有序链表，获取第 n 个节点的值
    for p <= n {
        // 取三个链表的最小结点
        minProduct = min(min(productA, productB), productC)
        p++
        // 前进最小结点对应链表的指针
        if minProduct == productA {
            productA += a
        }
        if minProduct == productB {
            productB += b
        }
        if minProduct == productC {
            productC += c
        }
    }
    return minProduct
}

func min(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

javascript 🤖

var nthUglyNumber = function(n, a, b, c) {
    // 可以理解为三个有序链表的头结点的值
    let productA = a, productB = b, productC = c;
    // 可以理解为合并之后的有序链表上的指针
    let p = 1;

    let minProduct = -666;

    // 开始合并三个有序链表，获取第 n 个节点的值
    while (p <= n) {
        // 取三个链表的最小结点
        minProduct = Math.min(productA, productB, productC);
        p++;
        // 前进最小结点对应链表的指针
        if (minProduct == productA) {
            productA += a;
        }
        if (minProduct == productB) {
            productB += b;
        }
        if (minProduct == productC) {
            productC += c;
        }
    }
    return minProduct;
};

这个思路应该是非常简单的，但是提交之后并不能通过所有测试用例，会超时。

注意题目给的数据范围非常大，a, b, c, n 的大小可以达到 10^9，所以即便上述算法的时间复杂度是 O(n)，也是相对比较耗时的，应该有更好的思路能够进一步降低时间复杂度。

这道题的正确解法难度比较大，难点在于你要把一些数学知识和二分搜索技巧结合起来才能高效解决这个问题。

首先，我们可以定义一个单调递增的函数 f：

f(num, a, b, c) 计算 [1..num] 中，能够整除 a 或 b 或 c 的数字的个数，显然函数 f 的返回值是随着 num 的增加而增加的（单调递增）。

题目让我们求第 n 个能够整除 a 或 b 或 c 的数字是什么，也就是说我们要找到一个最小的 num，使得 f(num, a, b, c) == n。

这个 num 就是第 n 个能够整除 a 或 b 或 c 的数字。

根据二分查找的实际运用给出的思路模板，我们得到一个单调函数 f，想求参数 num 的最小值，就可以运用搜索左侧边界的二分查找算法了：

java 🟢

int nthUglyNumber(int n, int a, int b, int c) {
    // 题目说本题结果在 [1, 2 * 10^9] 范围内，
    // 所以就按照这个范围初始化两端都闭的搜索区间
    int left = 1, right = (int) 2e9;
    // 搜索左侧边界的二分搜索
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (f(mid, a, b, c) < n) {
            // [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
            left = mid + 1;
        } else {
            // [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
            right = mid - 1;
        }
    }
    return left;
}

// 函数 f 是一个单调函数
// 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
long f(int num, int a, int b, int c) {
    // 下文实现
}

// ... 其他代码

cpp 🤖

int nthUglyNumber(int n, int a, int b, int c) {
    // 题目说本题结果在 [1, 2 * 10^9] 范围内，
    // 所以就按照这个范围初始化两端都闭的搜索区间
    int left = 1, right = 2e9;
    // 搜索左侧边界的二分搜索
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (f(mid, a, b, c) < n) {
            // [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
            left = mid + 1;
        } else {
            // [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
            right = mid - 1;
        }
    }
    return left;
}

// 函数 f 是一个单调函数
// 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
long f(int num, int a, int b, int c) {
    // 下文实现
}

// ... 其他代码

python 🤖

def nthUglyNumber(n: int, a: int, b: int, c: int) -> int:
    # 题目说本题结果在 [1, 2 * 10^9] 范围内，
    # 所以就按照这个范围初始化两端都闭的搜索区间
    left, right = 1, int(2e9)
    # 搜索左侧边界的二分搜索
    while left <= right:
        mid = left + (right - left) // 2
        if f(mid, a, b, c) < n:
            # [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
            left = mid + 1
        else:
            # [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
            right = mid - 1
    return left

# 函数 f 是一个单调函数
# 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
def f(num: int, a: int, b: int, c: int) -> int:
    # 下文实现
    pass

# ... 其他代码

go 🤖

func nthUglyNumber(n int, a int, b int, c int) int {
    // 题目说本题结果在 [1, 2 * 10^9] 范围内，
    // 所以就按照这个范围初始化两端都闭的搜索区间
    left, right := 1, int(2e9)
    // 搜索左侧边界的二分搜索
    for left <= right {
        mid := left + (right - left) / 2
        if f(mid, a, b, c) < n {
            // [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
            left = mid + 1
        } else {
            // [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
            right = mid - 1
        }
    }
    return left
}

// 函数 f 是一个单调函数
// 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
func f(num int, a int, b int, c int) int {
    // 下文实现
}

// ... 其他代码

javascript 🤖

var nthUglyNumber = function(n, a, b, c) {
    // 题目说本题结果在 [1, 2 * 10^9] 范围内，
    // 所以就按照这个范围初始化两端都闭的搜索区间
    let left = 1, right = 2 * 10 ** 9;
    // 搜索左侧边界的二分搜索
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        if (f(mid, a, b, c) < n) {
            // [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
            left = mid + 1;
        } else {
            // [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
            right = mid - 1;
        }
    }
    return left;
};

// 函数 f 是一个单调函数
// 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
var f = function(num, a, b, c) {
    // 下文实现
};

// ... 其他代码

搜索左侧边界的二分搜索代码模板在二分查找框架详解中讲过，没啥可说的，关键说一下函数 f 怎么实现，这里面涉及集合论定理以及最小公因数、最小公倍数的计算方法。

首先，我把 [1..num] 中能够整除 a 的数字归为集合 A，能够整除 b 的数字归为集合 B，能够整除 c 的数字归为集合 C，那么 len(A) = num / a, len(B) = num / b, len(C) = num / c，这个很好理解。

但是 f(num, a, b, c) 的值肯定不是 num / a + num / b + num / c 这么简单，因为你注意有些数字可能可以被 a, b, c 中的两个数或三个数同时整除，如下图：

按照集合论的算法，这个集合中的元素应该是：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C。结合上图应该很好理解。

问题来了，A, B, C 三个集合的元素个数我们已经算出来了，但如何计算像 A ∩ B 这种交集的元素个数呢？

其实也很容易想明白，A ∩ B 的元素个数就是 num / lcm(a, b)，其中 lcm 是计算最小公倍数（Least Common Multiple）的函数。

类似的，A ∩ B ∩ C 的元素个数就是 num / lcm(lcm(a, b), c) 的值。

现在的问题是，最小公倍数怎么求？

直接记住定理吧：lcm(a, b) = a * b / gcd(a, b)，其中 gcd 是计算最大公因数（Greatest Common Divisor）的函数。

现在的问题是，最大公因数怎么求？这应该是经典算法了，我们一般叫辗转相除算法（或者欧几里得算法）。

好了，套娃终于套完了，我们可以把上述思路翻译成代码就可以实现 f 函数，注意本题数据规模比较大，有时候需要用 long 类型防止 int 溢出：

java 🟢

class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        // 题目说本题结果在 [1, 2 * 10^9] 范围内，
        // 所以就按照这个范围初始化两端都闭的搜索区间
        int left = 1, right = (int) 2e9;
        // 搜索左侧边界的二分搜索
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (f(mid, a, b, c) < n) {
                // [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
                left = mid + 1;
            } else {
                // [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
                right = mid - 1;
            }
        }
        return left;
    }

    // 计算最大公因数（辗转相除/欧几里得算法）
    long gcd(long a, long b) {
        if (a < b) {
            // 保证 a > b
            return gcd(b, a);
        }
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    // 最小公倍数
    long lcm(long a, long b) {
        // 最小公倍数就是乘积除以最大公因数
        return a * b / gcd(a, b);
    }

    // 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
    long f(int num, int a, int b, int c) {
        long setA = num / a, setB = num / b, setC = num / c;
        long setAB = num / lcm(a, b);
        long setAC = num / lcm(a, c);
        long setBC = num / lcm(b, c);
        long setABC = num / lcm(lcm(a, b), c);
        // 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
        return setA + setB + setC - setAB - setAC - setBC + setABC;
    }
}

cpp 🤖

class Solution {
public:
    int nthUglyNumber(int n, int a, int b, int c) {
        // 题目说本题结果在 [1, 2 * 10^9] 范围内，
        // 所以就按照这个范围初始化两端都闭的搜索区间
        int left = 1, right = 2e9;
        // 搜索左侧边界的二分搜索
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (f(mid, a, b, c) < n) {
                // [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
                left = mid + 1;
            } else {
                // [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
                right = mid - 1;
            }
        }
        return left;
    }

    // 计算最大公因数（辗转相除/欧几里得算法）
    long gcd(long a, long b) {
        if (a < b) {
            // 保证 a > b
            return gcd(b, a);
        }
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    // 最小公倍数
    long lcm(long a, long b) {
        // 最小公倍数就是乘积除以最大公因数
        return a * b / gcd(a, b);
    }

    // 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
    long f(int num, int a, int b, int c) {
        long setA = num / a, setB = num / b, setC = num / c;
        long setAB = num / lcm(a, b);
        long setAC = num / lcm(a, c);
        long setBC = num / lcm(b, c);
        long setABC = num / lcm(lcm(a, b), c);
        // 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
        return setA + setB + setC - setAB - setAC - setBC + setABC;
    }
};

python 🤖

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        # 题目说本题结果在 [1, 2 * 10^9] 范围内，
        # 所以就按照这个范围初始化两端都闭的搜索区间
        left, right = 1, int(2e9)
        # 搜索左侧边界的二分搜索
        while left <= right:
            mid = left + (right - left) // 2
            if self.f(mid, a, b, c) < n:
                # [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
                left = mid + 1
            else:
                # [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
                right = mid - 1
        return left

    # 计算最大公因数（辗转相除/欧几里得算法）
    def gcd(self, a: int, b: int) -> int:
        if a < b:
            # 保证 a > b
            return self.gcd(b, a)
        if b == 0:
            return a
        return self.gcd(b, a % b)

    # 最小公倍数
    def lcm(self, a: int, b: int) -> int:
        # 最小公倍数就是乘积除以最大公因数
        return a * b // self.gcd(a, b)

    # 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
    def f(self, num: int, a: int, b: int, c: int) -> int:
        setA, setB, setC = num // a, num // b, num // c
        setAB = num // self.lcm(a, b)
        setAC = num // self.lcm(a, c)
        setBC = num // self.lcm(b, c)
        setABC = num // self.lcm(self.lcm(a, b), c)
        # 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
        return setA + setB + setC - setAB - setAC - setBC + setABC

go 🤖

func nthUglyNumber(n int, a int, b int, c int) int {
    // 题目说本题结果在 [1, 2 * 10^9] 范围内，
    // 所以就按照这个范围初始化两端都闭的搜索区间
    left, right := 1, int(2e9)
    // 搜索左侧边界的二分搜索
    for left <= right {
        mid := left + (right - left) / 2
        if f(mid, a, b, c) < n {
            // [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
            left = mid + 1
        } else {
            // [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
            right = mid - 1
        }
    }
    return left
}

// 计算最大公因数（辗转相除/欧几里得算法）
func gcd(a, b int) int {
    if a < b {
        // 保证 a > b
        return gcd(b, a)
    }
    if b == 0 {
        return a
    }
    return gcd(b, a % b)
}

// 最小公倍数
func lcm(a, b int) int {
    // 最小公倍数就是乘积除以最大公因数
    return a * b / gcd(a, b)
}

// 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
func f(num, a, b, c int) int {
    setA, setB, setC := num / a, num / b, num / c
    setAB := num / lcm(a, b)
    setAC := num / lcm(a, c)
    setBC := num / lcm(b, c)
    setABC := num / lcm(lcm(a, b), c)
    // 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
    return setA + setB + setC - setAB - setAC - setBC + setABC
}

javascript 🤖

var nthUglyNumber = function(n, a, b, c) {
    // 题目说本题结果在 [1, 2 * 10^9] 范围内，
    // 所以就按照这个范围初始化两端都闭的搜索区间
    let left = 1, right = 2 * 10 ** 9;
    // 搜索左侧边界的二分搜索
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        if (f(mid, a, b, c) < n) {
            // [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边
            left = mid + 1;
        } else {
            // [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边
            right = mid - 1;
        }
    }
    return left;
};

// 计算最大公因数（辗转相除/欧几里得算法）
var gcd = function(a, b) {
    if (a < b) {
        // 保证 a > b
        return gcd(b, a);
    }
    if (b === 0) {
        return a;
    }
    return gcd(b, a % b);
};

// 最小公倍数
var lcm = function(a, b) {
    // 最小公倍数就是乘积除以最大公因数
    return a * b / gcd(a, b);
};

// 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
var f = function(num, a, b, c) {
    let setA = Math.floor(num / a), setB = Math.floor(num / b), setC = Math.floor(num / c);
    let setAB = Math.floor(num / lcm(a, b));
    let setAC = Math.floor(num / lcm(a, c));
    let setBC = Math.floor(num / lcm(b, c));
    let setABC = Math.floor(num / lcm(lcm(a, b), c));
    // 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
    return setA + setB + setC - setAB - setAC - setBC + setABC;
};

实现了 f 函数，结合之前的二分搜索模板，时间复杂度下降到对数级别，即可高效解决这道题目了。

以上就是所有「丑数」相关的题目，用到的知识点有算术基本定理、合并多个有序链表、二分搜索模板、辗转相除法等等，如果没做过类似的题目可能很难想出来，但只要做过，也就手到擒来了。所以我说这种数学问题属于会者不难，难者不会的类型。

引用本文的题目

安装我的 Chrome 刷题插件点开下列题目可直接查看解题思路：

LeetCode	力扣
-	剑指 Offer 49. 丑数

一文秒杀所有丑数系列问题

1201. 丑数 III https://leetcode.cn/problems/ugly-number-iii

1201. Ugly Number III https://leetcode.com/problems/ugly-number-iii

263. 丑数 https://leetcode.cn/problems/ugly-number

263. Ugly Number https://leetcode.com/problems/ugly-number

264. 丑数 II https://leetcode.cn/problems/ugly-number-ii

264. Ugly Number II https://leetcode.com/problems/ugly-number-ii

313. 超级丑数 https://leetcode.cn/problems/super-ugly-number

313. Super Ugly Number https://leetcode.com/problems/super-ugly-number

剑指 Offer 49. 丑数 https://leetcode.cn/problems/chou-shu-lcof

剑指 Offer 49. 丑数 LCOF https://leetcode.com/problems/chou-shu-lcof

丑数 I

丑数 II

超级丑数

丑数 III