Java three methods, 23ms, 36 ms, 58ms(with heap), performance explained
Basic idea is same as ugly number II, new ugly number is generated by multiplying a prime with previous generated ugly number. One catch is need to remove dupli
Basic idea is same as ugly number II, new ugly number is generated by multiplying a prime with previous generated ugly number. One catch is need to remove duplicate\n\nLet's start with the **common solution** from ugly number II **36 ms, Theoretically O(kN)**\n\n    public int nthSuperUglyNumberI(int n, int[] primes) {\n        int[] ugly = new int[n];\n        int[] idx = new int[primes.length];\n    \n        ugly[0] = 1;\n        for (int i = 1; i < n; i++) {\n            //find next\n            ugly[i] = Integer.MAX_VALUE;\n            for (int j = 0; j < primes.length; j++)\n                ugly[i] = Math.min(ugly[i], primes[j] * ugly[idx[j]]);\n            \n            //slip duplicate\n            for (int j = 0; j < primes.length; j++) {\n                while (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;\n            }\n        }\n    \n        return ugly[n - 1];\n    }\n\n\nIf you look at the above solution, it has **redundant multiplication** can be avoided, and also two for loops can be consolidated into one. This **trade-off space for speed. 23 ms, Theoretically O(kN)**\n\n    public int nthSuperUglyNumber(int n, int[] primes) {\n            int[] ugly = new int[n];\n            int[] idx = new int[primes.length];\n            int[] val = new int[primes.length];\n            Arrays.fill(val, 1);\n    \n            int next = 1;\n            for (int i = 0; i < n; i++) {\n                ugly[i] = next;\n                \n                next = Integer.MAX_VALUE;\n                for (int j = 0; j < primes.length; j++) {\n                    //skip duplicate and avoid extra multiplication\n                    if (val[j] == ugly[i]) val[j] = ugly[idx[j]++] * primes[j];\n                    //find next ugly number\n                    next = Math.min(next, val[j]);\n                }\n            }\n    \n            return ugly[n - 1];\n        }\n\nCan we do better? Theoretically yes, by keep the one candidates for each prime in a **heap**, it can improve the theoretical bound to **O( log(k)N )**, but in reality it's **58 ms**. I think it's the result of using higher level object instead of primitive. Can be improved by writing an **index heap** (http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html)\n\n\n    public int nthSuperUglyNumberHeap(int n, int[] primes) {\n        int[] ugly = new int[n];\n    \n        PriorityQueue<Num> pq = new PriorityQueue<>();\n        for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));\n        ugly[0] = 1;\n    \n        for (int i = 1; i < n; i++) {\n            ugly[i] = pq.peek().val;\n            while (pq.peek().val == ugly[i]) {\n                Num nxt = pq.poll();\n                pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));\n            }\n        }\n    \n        return ugly[n - 1];\n    }\n    \n    private class Num implements Comparable<Num> {\n        int val;\n        int idx;\n        int p;\n    \n        public Num(int val, int idx, int p) {\n            this.val = val;\n            this.idx = idx;\n            this.p = p;\n        }\n    \n        @Override\n        public int compareTo(Num that) {\n            return this.val - that.val;\n        }\n    }
['Heap (Priority Queue)', 'Java']