写一个程序来找第 n 个超级丑数。 超级丑数是所有的质数因子都在给定的的质数集合内的正整数。 比如给定质数集合 [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 k 是丑数集合的长度
在线评测地址
样例 1: 输入: n = 6, [2,7,13,19] 输出: 13
样例 2: 输入: n = 11, [2,3,5] 输出: 15
[题解]
做法 1:
使用小根堆, 初始将 1 放入堆, 循环 n-1 次, 每次取出堆顶, 然后将该值与素数列表每个数的乘积再次放入堆. 注意可能会有数重复入堆, 所以还需要额外的数据结构记录一个数是否出现过, 把重复的数排除, 以保证取出的堆顶是从小到大的超级丑数. n-1 次循环之后, 此时的堆顶即是第 n 个丑数. 时间复杂度 O(nklogn)
做法 2:
依次求出前 n 个超级丑数. 定义 times[i]表示当前的超级丑数的质因数中, 列表中第 i 个素数的次数. uglys[i]表示第 i+1 个素数. 初始 times[i] = 0, uglys[0] = 1, 然后依次由 uglys[0] ~ uglys[i] 求出 uglys[i+1]: 枚举, 求出 uglys[times[j]] * prime[j] 的最小值, 即是 uglys[i+1] 更新对应的 times[j], 即 若 uglys[times[j]] * prime[j] == uglys[i+1], times[j]++ 时间复杂度 O(nk) 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[] times = new int[primes.length]; int[] uglys = new int[n]; uglys[0] = 1; for (int i = 1; i < n; i++) { uglys[i] = Integer.MAX_VALUE; for (int j = 0; j < primes.length; j++) { uglys[i] = Math.min(uglys[i], primes[j] * uglys[times[j]]); } for (int j = 0; j < times.length; j++) { if (uglys[times[j]] * primes[j] == uglys[i]) { times[j]++; } } } return uglys[n - 1]; } }
更多题解参见