264. 丑数 II

Problem: 264. 丑数 II

思路

这道题目关键在于理解丑数的生成规律。丑数就是质因子只包含 2、3 和 5 的正整数。因此我们可以创建一个dp数组用来保存计算丑数的子过程。在这个过程中只要保证数据是那个小到大生成的就可以了。

解题方法

1.初始化丑数数组dp，dp[1] = 1，表示第一个丑数为1。
2.初始化三个指针i2、i3、i5，都指向第一个丑数。
3.每次生成新的丑数，都是从dp[i2]*2、dp[i3]*3、dp[i5]*5这三个数中取最小的一个，作为新的丑数。这个新的丑数就是下一个丑数。
4.将数值等于丑数的数字指针向后移动一步
重复步骤3~4，直到找到第n个丑数。

复杂度

时间复杂度:

$O(n)$。因为要遍历一遍数组

空间复杂度:

$O(n)$。额外空间dp数组。

Code

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2, i2 = 1, i3 = 1, i5 = 1, a, b, c; i <= n; i++) {
            a = dp[i2] * 2;
            b = dp[i3] * 3;
            c = dp[i5] * 5;
            int cur = Math.min(a, Math.min(b, c));
            if (cur == a) {
                i2++;
            }
            if (cur == b) {
                i3++;
            }
            if (cur == c) {
                i5++;
            }
            dp[i] = cur;

        }
        return dp[n];
    }
}