面试题49

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

• 1 是丑数。

• n 不超过1690。

注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

Solutions

1. dynamic programming

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n); dp[0] = 1;
        int i2, i3, i5, num2, num3, num5;
        i2 = i3 = i5 = 0;

        for (int i = 1; i < n; i++) {
            num2 = dp[i2] * 2;
            num3 = dp[i3] * 3;
            num5 = dp[i5] * 5;
            int minval = min(num2, min(num3, num5));
            dp[i] = minval;
            if (num2 == minval)
                i2++;
            if (num3 == minval)
                i3++;
            if (num5 == minval)
                i5++;
        }

        return dp[n - 1];
    }
};