313. Super Ugly Number

一刷 06/2022

这道题和264最大的区别就是在选择next的时候，264只有2，3，5三个factor，所以取min是O(1) time 但是这道题有k个prime numbers，取min就是O(K) time 这时候我们需要priority queue 来获得当前最小的next number

写了一个debug了一个小时的bug -> 在更新dp[i++]之前插入new Tuple的话就会导致new Tuple的pointer在i之后，导致sift up的时候用来compare的值全都是0

Time O(N logK)

Space O(K) -> for heap

Runtime: 113 ms, faster than 59.84% of Java online submissions for Super Ugly Number.

Memory Usage: 53.2 MB, less than 31.08% of Java online submissions for Super Ugly Number.

class Solution {

    class Tuple {

        public int prime;

        public int pointer;

        public Tuple(int prime, int pointer) {

            this.prime = prime;

            this.pointer = pointer;

        }

    }

    public int nthSuperUglyNumber(int n, int[] primes) {

        int[] dp = new int[n];

        dp[0] = 1;

        PriorityQueue<Tuple> pq = new PriorityQueue<>((a, b) -> {

            return a.prime * dp[a.pointer] - b.prime * dp[b.pointer];

            });

        for (int prime : primes) {

            pq.offer(new Tuple(prime, 0));

        }

        int i = 1;

        while (i < n) {

            Tuple curr = pq.poll();

            int next = curr.prime * dp[curr.pointer];

            if (next != dp[i - 1]) {

                dp[i++] = next;

            }

            pq.add(new Tuple(curr.prime, curr.pointer + 1));

        }

        return dp[n - 1];

    }

}