🌕 313. 超级丑数

难度: 🌕

问题描述

---

解法

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        // 思路：
        // 找一个数组，存放所有质因数对应的指针，质因数需要与指针下的数相乘，取所有的最小值，更新指针
        int len = primes.length;
        int[] array = new int[len];
        Arrays.fill(array, 1); // 初始指针均指向 下标 1，即 dp[1] = 1
        // 用 long 防止超范，虽然题意保证了 min 在 int 范围内，但无法确保该轮其他值也在 int 范围内
        long[] dp = new long[n + 1];
        dp[1] = 1;
        for(int i = 2; i <= n; i ++) {
            // 求 每个质因数当前指针下的最小值
            long min = dp[array[0]] * primes[0];
            for(int j = 1; j < len; j ++) {
                min = Math.min(min, dp[array[j]] * primes[j]);
            }
            dp[i] = min;
            // 更新相关指针
            for(int j = 0; j < len; j ++) {
                if(primes[j] * dp[array[j]] == min) {
                    array[j] ++;
                }
            }
        }
        return (int)dp[n];
    }
}

---

输出