剑指 Offer 49. 丑数

剑指 Offer 49. 丑数

• 解题思路
• 代码

解题思路

这题要用动态规划。

丑数只包含因子 2, 3, 5 ，因此有 “丑数 == 某较小丑数× 某因子” （例如：10 = 5*2）。
所以我们要得到多大的丑数就要给每一个丑数都求出来它可能变成的丑数，比如1 它可以变成1*2=2 、1*3=3、1*5=5，但是如果每个数都这样乘，搞不清顺序的，所以要用三个指针来分别记录×2/3/5这三种情况！

dp数组含义： dp[i] 代表第 i+1 个丑数；

状态转移方程：
因为我们求的丑数要按照从小到大的顺序来放，所以要放的丑数就是三个情况中最小的那个。
dp[i] = Math.min(Math.min(aa, bb), cc);

算法步骤：

• 此题只需要理解为三个数组的合并即可。一个数组只乘2，一个数组只乘3，一个数组只乘5。
• 合并时比较，谁小就插入谁，并将对应数组指针+1.

代码

class Solution {
    public int nthUglyNumber(int n) {
        //三指针， 用到了那个，那个就加一

        int a = 0;
        int b = 0;
        int c = 0;
// dp[i] 代表第 i + 1i+1 个丑数；
        int[] dp = new int[n];
        //base case
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            int aa = dp[a] * 2;
            int bb = dp[b] * 3;
            int cc = dp[c] * 5;

            dp[i] = Math.min(Math.min(aa, bb), cc);
            if (dp[i] == aa) {
                a++;// 第a个数已经通过乘2得到了一个新的丑数，那下个需要通过乘2得到一个新的丑数的数应该是第(a+1)个数
            }
            if (dp[i] == bb) {
                b++;// 第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数
            }
            if (dp[i] == cc) {
                c++;// 第 c个数已经通过乘5得到了一个新的丑数，那下个需要通过乘5得到一个新的丑数的数应该是第(c+1)个数
            }
        }
        return dp[n - 1];
    }
}