LC 264. 丑数 II

题目描述

这是 LeetCode 上的 264. 丑数 II ，难度为 中等。

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和 5 的正整数。

示例 1：

输入：n = 10

输出：12

解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1

输出：1

解释：1 通常被视为丑数。

提示：

• $1 <= n <= 1690$

---

基本思路

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

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

---

优先队列（小根堆）

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

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

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

Java 代码：

class Solution {
    int[] nums = new int[]{2,3,5};
    public int nthUglyNumber(int n) {
        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;
    }
}

Python 代码：

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        nums = [2,3,5]
        explored = {1}
        pq = [1]
        for i in range(1, n+1):
            x = heapq.heappop(pq)
            if i == n:
                return x
            for num in nums:
                t = num * x
                if t not in explored:
                    explored.add(t)
                    heapq.heappush(pq,t)
        return -1

C++ 代码：

class Solution {
public:
    int nthUglyNumber(int n) {
        int nums[] = {2, 3, 5};
        set<long> s;
        priority_queue<long, vector<long>, greater<long>> q;
        s.insert(1);
        q.push(1);
        for (int i = 1; i <= n; i++)
        {
            long x = q.top();
            q.pop();
            if (i == n)
                return (int)x;
            for (int num = 0; num < 3; num++)
            {
                long t = nums[num] * x;
                if (!s.count(t))
                {
                    s.insert(t);
                    q.push(t);
                }
            }
        }
        return -1;
    }
};

• 时间复杂度：从优先队列中取最小值为 $O(1)$，往优先队列中添加元素复杂度为 $O(\log{n})$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：$O(n)$

---

多路归并（多指针）

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

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

• 由丑数 $\times 2$ 所得的有序序列：$1 \times 2$、$2 \times 2$、$3 \times 2$、$4 \times 2$、$5 \times 2$、$6 \times 2$、$8 \times 2$ …
• 由丑数 $ \times 3$ 所得的有序序列：$1 \times 3$、$2 \times 3$、$3 \times 3$、$4 \times 3$、$5 \times 3$、$6 \times 3$、$8 \times 3$ …
• 由丑数 $\times 5$ 所得的有序序列：$1 \times 5$、$2 \times 5$、$3 \times 5$、$4 \times 5$、$5 \times 5$、$6 \times 5$、$8 \times 5$ …

举个🌰，假设我们需要求得 $[1, 2, 3, … , 10, 12]$ 丑数序列 $arr$ 的最后一位，那么该序列可以看作以下三个有序序列归并而来：

• $1 \times 2, 2 \times 2, 3 \times 2, … , 10 \times 2, 12 \times 2$ ，将 $2$ 提出，即 $arr \times 2$
• $1 \times 3, 2 \times 3, 3 \times 3, … , 10 \times 3, 12 \times 3$ ，将 $3$ 提出，即 $arr \times 3$
• $1 \times 5, 2 \times 5, 3 \times 5, … , 10 \times 5, 12 \times 5$ ，将 $5$ 提出，即 $arr \times 5$

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

Java 代码：

class Solution {
    public int nthUglyNumber(int n) {
        // 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];
    }
}

Python 代码：

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        # ans 用作存储已有丑数（从下标 1 开始存储，第一个丑数为 1）
        ans = [0] * (n+1)
        ans[1] = 1
        # 由于三个有序序列都是由「已有丑数」*「质因数」而来
        # i2、i3 和 i5 分别代表三个有序序列当前使用到哪一位「已有丑数」下标（起始都指向 1）
        i2 = i3 = i5 = 1
        idx = 2
        while idx <= n:
            # 由 ans[iX] * X 可得当前有序序列指向哪一位
            a,b,c = ans[i2] *2,ans[i3]*3,ans[i5]*5
            # 将三个有序序列中的最小一位存入「已有丑数」序列，并将其下标后移
            m = min(a,b,c)
            # 由于可能不同有序序列之间产生相同丑数，因此只要一样的丑数就跳过（不能使用 else if ）
            if m == a:
                i2 += 1
            if m == b:
                i3 += 1
            if m == c:
                i5 += 1
            ans[idx] = m
            idx += 1
        return ans[n]

JavaScript 代码：

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function(n) {
    const ans=new Array(n+1);
    ans[1]=1;
    for(let i2=1, i3=1, i5=1, idx=2;idx<=n;idx++){
        let a=ans[i2]*2, b=ans[i3]*3, c=ans[i5]*5;
        let min=Math.min(a, b, c);
        if(min===a) i2++;
        if(min===b) i3++;
        if(min===c) i5++;
        ans[idx]=min;
    }
    return ans[n];
};

C++ 代码：

class Solution {
public:
    int nthUglyNumber(int n) {
        // 存储丑数
        int *arr = new int[n + 1];
        arr[1] = 1;
        
        for (int x = 1, y = 1, z = 1, index = 2; index <= n; index++){
            int a = arr[x] * 2, b = arr[y] * 3, c = arr[z] * 5;
            int m = min(a, min(b, c));
            if (m == a)x++;
            if (m == b)y++;
            if (m == c)z++;
            arr[index] = m;
        }
        int ans = arr[n];
        delete[] arr;
        return ans;
    }
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.264 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。