算法记录

LeetCode 题目：

   超级丑数是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

  给你一个整数 n 和一个整数数组 primes，返回第 n 个超级丑数 。

&emsp;&emsp;题目数据保证第 n 个超级丑数在 32-bit 带符号整数范围内。 <hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

说明

一、题目

输入：n = 12, primes = [2,7,13,19]输出：32 解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

二、分析

这个题和丑数计算方式就多了一个变量数组而已，丑数是只有三个质因子，这个超级丑数的质因子变成了变量数组。

只需要按照丑数的做法，只不过把所有的变量换成中间数组来存储就可以了。

class Solution {    public int nthSuperUglyNumber(int n, int[] primes) {        int m = primes.length;        int[] index = new int[m], ret = new int[n + 1], nums = new int[m];        for(int i = 1; i <= n; i++) {            int min = Arrays.stream(nums).min().getAsInt();            ret[i] = min == 0 ? 1 : min;            for(int j = 0; j < m; j++) {                if(min == nums[j]) {                    index[j]++;                    nums[j] = ret[index[j]] * primes[j];                }            }        }        return ret[n];    }}

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

总结

动态规划。

原文：https://juejin.cn/post/7103885112961400862