0动态规划 LeetCodde313. 超级丑数

分析

动态规划 多路归并
丑数」都是基于「已有丑数」而来（使用「已有丑数」乘上「给定质因数」primes[i]primes[i]）。
超级丑数的生成可以看作是如下三个序列合并成有序数组的过程。
因此，如果我们所有丑数的有序序列为 a1,a2,a3,…,ana1,a2,a3,…,an 的话，序列中的每一个数都必然能够被以下三个序列（中的至少一个）覆盖（这里假设 primes = [2,3,5]primes=[2,3,5]）：

由丑数 * 22 所得的有序序列：1 * 21∗2、2 * 22∗2、3 * 23∗2、4 * 24∗2、5 * 25∗2、6 * 26∗2、8 * 28∗2 …
由丑数 * 33 所得的有序序列：1 * 31∗3、2 * 32∗3、3 * 33∗3、4 * 34∗3、5 * 35∗3、6 * 36∗3、8 * 38∗3 …
由丑数 * 55 所得的有序序列：1 * 51∗5、2 * 52∗5、3 * 53∗5、4 * 54∗5、5 * 55∗5、6 * 56∗5、8 * 58∗5 …

两个相同大小的超级丑数会相遇，一起给结果数组赋值，因此不用担心会重复。
https://leetcode.cn/problems/super-ugly-number/solution/gong-shui-san-xie-yi-ti-shuang-jie-you-x-jyow/

class Solution {
    
    public int nthSuperUglyNumber(int n, int[] primes) {
    
int m = primes.length;
        int[] ugly = new int[m];
        long[] ans = new long[n];
        ans[0] = 1;
        for (int i = 1; i < n; i++) {
    
            int tmp = Integer.MAX_VALUE;
            for (int j = 0; j < m; j++) {
    
                tmp = (int)Math.min(tmp,ans[ugly[j]] * primes[j]);
            }
            ans[i] = tmp;
            for (int j = 0; j < m; j++) {
    
                if (tmp == ans[ugly[j]] * primes[j]) {
    
                    ugly[j] += 1;
                }
            }
        }
        return (int)ans[n-1];
    }
}