leetCode-313:Super Ugly Number

问题描述

给定一个正整数 n 和一个素数数组，定义“超级丑数”为因子只能是素数数组中的数（1 是“超级丑数”）。要求找出第 n 个“超级丑数”。题目链接：**点我**

样例输入输出

输入：n = 12, primes = [2,7,13,19]

输出：32

解释：超级丑数列表为：[1,2,4,7,8,13,14,16,19,26,28,32]

输入：n = 1, primes = [2]

输出：1

问题解法

此题与 LeetCode-264 类似，解法也类似，只不过把原先固定的 [2, 3, 5] 数组换成输入的素数数组即可。代码如下

class Solution
{
    public int nthSuperUglyNumber(int n, int[] primes)
    {
        int[] points = new int[primes.length];
        int[] currents = new int[primes.length];
        int[] results = new int[n];
        results[0] = 1;
        for (int i = 2; i <= n; i++)
        {
            int minNum = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j++)
            {
                currents[j] = primes[j] * results[points[j]];
                minNum = Math.min(minNum, currents[j]);
            }
            
            for (int j = 0; j < primes.length; j++)
            {
                if (currents[j] == minNum)
                {
                    points[j]++;
                }
            }
            
            results[i - 1] = minNum;
        }
        
        return results[n - 1];
    }
}