313. Super Ugly Number

LeetCode Math Heap

Write a program to find the $n^{th}$ super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size $k$.

Example:

Input: n = 12, primes = [2,7,13,19]
Output: 32 
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 
             super ugly numbers given primes = [2,7,13,19] of size 4.

Note:

• 1 is a super ugly number for any given primes.
• The given numbers in primes are in ascending order.
• $0 < k ≤ 100, 0 < n ≤ 106, 0 <$ primes[i] $< 1000$.
• The $n^{th}$ super ugly number is guaranteed to fit in a 32-bit signed integer.

分析

LeetCode 264. Ugly Number II的升级版。前者规定2、3、5为丑数仅有的质因数。现在需要考虑给定的任意质因数集合，构造出第$n$个超级丑数。

public int nthSuperUglyNumber(int n, int[] primes) {
    if (n < 0 || primes == null || primes.length == 0)
        throw new IllegalArgumentException();
    // 超级丑数
    int[] uglyNumber = new int[n];
    uglyNumber[0] = 1;
    // pointers存储的是uglyNumber的位置
    int[] pointers = new int[primes.length];
    int next = 0;   // 下一个超级丑数
    int pos = 0;    // 下一个超级丑数的位置
    for (int i = 1; i < n; i++) {
        // 找寻下一个超级丑数
        next = Integer.MAX_VALUE;
        pos = 0;
        for (int j = 0; j < primes.length; j++) {
            int cur = primes[j] * uglyNumber[pointers[j]];
            if (cur < next) {
                next = cur;
                pos = j;
            }
        }
        // 找到了，更新超级丑数
        uglyNumber[i] = next;
        // 超级丑数对应的位置+1，考虑所有质数是为了消除重复
        for (int j = 0; j < primes.length; j++)
            if (next == uglyNumber[pointers[j]] * primes[j]) pointers[j]++;
    } // end for
    return uglyNumber[n - 1];
}