超级丑数

一份执着✘

发布于 2018-06-04 16:52:07

8790

发布于 2018-06-04 16:52:07

文章被收录于专栏：赵俊的Java专栏

题意

写一个程序来找第 n 个超级丑数。

超级丑数的定义是正整数并且所有的质数因子都在所给定的一个大小为 k 的质数集合内。

比如给你 4 个质数的集合 [2, 7, 13, 19], 那么 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 是前 12 个超级丑数。

注意事项

1 永远都是超级丑数不管给的质数集合是什么。
给你的质数集合已经按照升序排列。
0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000

样例

给出 n = 6 和质数集合 [2, 7, 13, 19]。第 6 个超级丑数为 13，所以返回 13 作为结果。

思路

这道题其实就是丑数II 的加强版，只是原来的丑数定义质因子是固定的 3 个，现在是自定义的质因子。

只需要将丑数II 中的 lastUgly 用数组存放起来即可，其他思路还是一样的。

代码实现

public class Solution {
    /**
     * @param n a positive integer
     * @param primes the given prime list
     * @return the nth super ugly number
     */
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] uglys = new int[n];
        int[] idxPrimes = new int[primes.length];
        uglys[0] = 1;
        
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            
            for (int j = 0; j < primes.length; j++) {
                min = Math.min(min, primes[j] * uglys[idxPrimes[j]]);
            }
            uglys[i] = min;
            
            for (int j = 0; j < primes.length; j++) {
                if (primes[j] * uglys[idxPrimes[j]] == min) {
                    idxPrimes[j]++;                    
                }
            }
        }
        return uglys[n - 1];
    }
}