49. 丑数

Leetcode

题目描述

把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上把 1 当作第一个丑数。求按从小到大的顺序的第 N 个丑数。

解题思路

除了 1，每个丑数都是某个更小的丑数乘以 2、3 或 5 得到的。dp 按从小到大的顺序保存丑数，i2、i3、i5 分别指向下一个要乘以 2、3、5 的丑数，三个乘积中最小的就是下一个丑数。哪个指针产生了它，就把哪个指针后移；6 = 3 × 2 = 2 × 3 这类乘积相等的情况，两个指针同时后移，避免重复。

例如已经得到 1, 2, 3, 4, 5, 6 时，i2、i3、i5 分别指向 4、3、2，三个候选为 8、9、10，下一个丑数是 8，i2 后移到 5。

public int nthUglyNumber(int n) {
    if (n <= 6)
        return n;
    int i2 = 0, i3 = 0, i5 = 0;
    int[] dp = new int[n];
    dp[0] = 1;
    for (int i = 1; i < n; i++) {
        int next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;
        dp[i] = Math.min(next2, Math.min(next3, next5));
        if (dp[i] == next2)
            i2++;
        if (dp[i] == next3)
            i3++;
        if (dp[i] == next5)
            i5++;
    }
    return dp[n - 1];
}