🌕 剑指 Offer 49. 丑数

难度: 🌕

问题描述

---

解法

class Solution {
    public int nthUglyNumber(int n) {
        // 思路：
        // 每次在 {2[a], 3[b], 5[c]} 中取 min
        // [a], [b], [c] 本身也是丑数，a, b, c 是丑数数组下标
        int a = 0;
        int b = 0;
        int c = 0;
        int[] dp = new int[n];
        dp[0] = 1;

        for(int i = 1; i < n; i ++) {
            int cur = Math.min(2 * dp[a], Math.min(3 * dp[b], 5 * dp[c]));
            if(cur == 2 * dp[a]) {
                a ++;
            }
            if(cur == 3 * dp[b]) {
                b ++;
            }
            if(cur == 5 * dp[c]) {
                c ++;
            }
            dp[i] = cur;
        }
        return dp[n - 1];
    }
}

---

输出