Super Ugly Number

https://leetcode.com/problems/super-ugly-number/description/

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [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) 1 is a super ugly number for any given primes.

(2) The given numbers in primes are in ascending order.

(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

Thoughts

和ugly number一个思路，只是这次要维持k个指针，因此用一个数组存储每个指针当前所在的位置。

每次对k个指针找出乘以相应prime最小的数。

Code

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] f = new int[n];
        f[0] = 1;
        int[] g = new int[primes.length];

        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE, minIndex = -1;
            for (int j = 0; j < g.length; j++) {
                if (f[g[j]] * primes[j] < min) {
                    minIndex = j;
                    min = f[g[j]] * primes[j];
                }
            }
            g[minIndex]++;

            if (min == f[i - 1]) {
                i--;
            } else {
                f[i] = min;
            }
        }

        return f[n - 1];
    }
}

Analysis

Errors:

1. 丑数可能有重复的

2. 重复时，不应n++, 而应维持i不变

时间复杂度O(nk).

Ver2.

我们可以把每个指针指向的元素存到min heap中，这样就能理论上O(1)时间找出最小了。总时间为O(nlgk)

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] f = new int[n];
        f[0] = 1;
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> a[0] - b[0]
        );
        for (int i = 0; i < primes.length; i++) {
            pq.offer(new int[]{f[0] * primes[i], primes[i], 0});
        }

        for (int i = 1; i < n; i++) {
            int[] min = pq.poll();
            if (min[0] == f[i - 1]) {
                i--;
            } else {
                f[i] = min[0];
            }

            pq.offer(new int[]{f[min[2] + 1] * min[1], min[1], min[2] + 1});
        }

        return f[n - 1];
    }
}

Errors: 1. pq.offer要写到后面，因为现在pointer指向的是下一个要访问的位置，如果不先更新f[i]则会导致溢出。