基本思路

根据丑数的定义，我们有如下结论：

  • 是最小的丑数。
  • 对于任意一个丑数 ，其与任意的质因数（、、）相乘，结果（、、）仍为丑数。

优先队列（小根堆）解法

有了基本的分析思路，一个简单的解法是使用优先队列：

  1. 起始先将最小丑数 放入队列
  2. 每次从队列取出最小值 ，然后将 所对应的丑数 、 和 进行入队。
  3. 对步骤 2 循环多次，第 次出队的值即是答案。

为了防止同一丑数多次进队，我们需要使用数据结构 来记录入过队列的丑数。

代码：

import java.util.*;
public class Solution {
    int[] nums = new int[]{2,3,5};
    public int GetUglyNumber_Solution(int n) {
        if (n == 0) return 0;
        Set<Long> set = new HashSet<>();
        Queue<Long> pq = new PriorityQueue<>();
        set.add(1L);
        pq.add(1L);
        for (int i = 1; i <= n; i++) {
            long x = pq.poll();
            if (i == n) return (int)x;
            for (int num : nums) {
                long t = num * x;
                if (!set.contains(t)) {
                    set.add(t);
                    pq.add(t);
                }
            }
        }
        return -1;
    }
}
  • 时间复杂度：从优先队列中取最小值为 ，往优先队列中添加元素复杂度为 。整体复杂度为
  • 空间复杂度：

多路归并（多指针）解法

从解法一中不难发现，我们「往后产生的丑数」都是基于「已有丑数」而来（使用「已有丑数」乘上「质因数」、、）。

因此，如果我们所有丑数的有序序列为 的话，序列中的每一个数都必然能够被以下三个序列（中的至少一个）覆盖：

  • 由丑数 * 所得的有序序列：、、、、、、 ...
  • 由丑数 * 所得的有序序列：、、、、、、 ...
  • 由丑数 * 所得的有序序列：、、、、、、 ...

举个🌰，假设我们需要求得 丑数序列 的最后一位，那么该序列可以看作以下三个有序序列归并而来：

  • ，将 提出，即
  • ，将 提出，即
  • ，将 提出，即

因此我们可以使用三个指针来指向目标序列 的某个下标（下标 作为哨兵不使用，起始都为 ），使用 代表当前使用到三个有序序列中的哪一位，同时使用 表示当前生成到 哪一位丑数。

代码：

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int n) {
        if (n == 0) return 0;
        // ans 用作存储已有丑数（从下标 1 开始存储，第一个丑数为 1）
        int[] ans = new int[n + 1];
        ans[1] = 1;
        // 由于三个有序序列都是由「已有丑数」*「质因数」而来
        // i2、i3 和 i5 分别代表三个有序序列当前使用到哪一位「已有丑数」下标（起始都指向 1）
        for (int i2 = 1, i3 = 1, i5 = 1, idx = 2; idx <= n; idx++) {
            // 由 ans[iX] * X 可得当前有序序列指向哪一位
            int a = ans[i2] * 2, b = ans[i3] * 3, c = ans[i5] * 5;
            // 将三个有序序列中的最小一位存入「已有丑数」序列，并将其下标后移
            int min = Math.min(a, Math.min(b, c));
            // 由于可能不同有序序列之间产生相同丑数，因此只要一样的丑数就跳过（不能使用 else if ）
            if (min == a) i2++; 
            if (min == b) i3++;
            if (min == c) i5++;
            ans[idx] = min;
        }
        return ans[n];
    }
}
  • 时间复杂度：
  • 空间复杂度：

最后

这是我们「剑指 の 精选」系列文章的第 No.33 篇，系列开始于 2021/07/01。

该系列会将牛客网「剑指 Offer」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)