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. 丑数的定义是质因子只包含 2、3 和 5 的正整数。换句话说，丑数可以表示为 2^i * 3^j * 5^k 的形式，其中 i、j、k 是非负整数。

2. 为了找到第 n 个丑数，我们可以使用动态规划的方法。我们维护一个数组 ugly 来存储前 n 个丑数，并使用三个指针 i2、i3 和 i5 来分别跟踪下一个乘以 2、3 和 5 的丑数的位置。

3. 每次我们计算下一个丑数时，取 ugly[i2] * 2、ugly[i3] * 3 和 ugly[i5] * 5 中的最小值作为下一个丑数，并相应地移动指针。

算法时间复杂度： O(n)，因为我们需要计算 n 个丑数。

三、正确性证明

为什么这种思路是正确的？

1. 丑数的生成：每个丑数都是通过已有的丑数乘以 2、3 或 5 得到的。因此，通过维护三个指针，我们确保了所有可能的丑数都能被考虑到。
2. 避免重复：当多个候选值相同时，我们会同时移动对应的指针，确保不会重复计算相同的丑数。
3. 有序性：由于我们总是选择最小的候选值作为下一个丑数，因此生成的丑数序列是有序的。

数学证明

1. 基础：1 是第一个丑数，符合定义。
2. 归纳假设：假设前 k 个丑数已经正确生成。
3. 归纳步骤：第 k+1 个丑数是通过前 k 个丑数乘以 2、3 或 5 得到的最小值。由于我们已经正确生成了前 k 个丑数，且通过指针确保了所有可能的乘积都被考虑到，因此第 k+1 个丑数也是正确的。
4. 结论：通过数学归纳法，我们证明了该算法能够正确生成第 n 个丑数。

三、代码实现

class Solution {
    public int nthUglyNumber(int n) {
        if (n <= 0) return 0;
        
        int[] ugly = new int[n];
        ugly[0] = 1;  // 第一个丑数是1
        
        // 三个指针：分别指向下一个要乘以2、3、5的丑数
        int i2 = 0, i3 = 0, i5 = 0;
        
        for (int i = 1; i < n; i++) {
            // 计算三个候选值
            int next2 = ugly[i2] * 2;
            int next3 = ugly[i3] * 3;
            int next5 = ugly[i5] * 5;
            
            // 选择最小的作为下一个丑数
            int nextUgly = Math.min(next2, Math.min(next3, next5));
            ugly[i] = nextUgly;
            
            // 更新指针：哪个候选值被选中了，哪个指针就前进
            // 注意：可能有多个候选值相同，需要都前进（避免重复）
            if (nextUgly == next2) i2++;
            if (nextUgly == next3) i3++;
            if (nextUgly == next5) i5++;
        }
        
        return ugly[n - 1];
    }
}

四、扩展

LeetCode 313. 超级丑数：

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

示例 1： 输入：n = 12, primes = [2,7,13,19] 输出：32 解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

代码实现

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int k = primes.length;
        long[] ugly = new long[n];  // 使用long避免溢出
        ugly[0] = 1;
        
        // 每个质数一个指针，指向下一个要乘以该质数的丑数
        int[] pointers = new int[k];
        
        for (int i = 1; i < n; i++) {
            // 找到所有候选值中的最小值
            long minVal = Long.MAX_VALUE;
            for (int j = 0; j < k; j++) {
                long candidate = ugly[pointers[j]] * primes[j];
                minVal = Math.min(minVal, candidate);
            }
            ugly[i] = minVal;
            
            // 更新所有产生最小值的指针
            for (int j = 0; j < k; j++) {
                if (ugly[pointers[j]] * primes[j] == minVal) {
                    pointers[j]++;
                }
            }
        }
        
        return (int)ugly[n - 1];
    }
}