Python O(nlogk) Concise Heap Solution and Detailed Explanation
The high level idea is to generate all ugly numbers in an array. To keep them in order, we need to pick a prime to multiply with a generated ugly number to gene
The high level idea is to generate all ugly numbers in an array. To keep them in order, we need to pick a prime to multiply with a generated ugly number to generate the "next" ugly number, or the smallest ugly number that hasn\'t been generated.\n\nSo we can generate a candidate minheap that guarantees to contain the next smallest ugly number and we can easily pop the smallest ugly number from it and add it to the ugly list. Any ugly number must be in form of ```p * u``` where ```p``` is a prime from ```primes``` list and ```u``` is a generated number in ugly list. So we just need to track currently smallest ```p * u``` that each ```p``` can generate and add them to the minheap. \n\nInitially, candidate minheap contains all the ```p``` in primes. Then each time we pop out a ```p * u```, we add ```p * u\'``` with the smallest ```u\'``` that ```p``` yet to use to the candidate list to ensure there is no ```p * u\'\'``` that can be smaller than ```p * u\'``` and missed by candidate list. Since ugly list is actually sorted, ```u\'``` is the next element of ```u```. \n\nIn such way, the candidates minheap limit its size within ```primes.length``` and won\'t miss any smallest ugly number as well.\n\nI tracked which ```p``` generates one specific ugly number ```x = p * u```, and an index ```i``` to track the smallest ```u``` or ```ugly[i]``` that specific ```p``` hasn\'t been multiplied with. Thus each heap element is a triple of ```(p*u, p, i)```\nAnd there could be identical value generated by different ```p```. e.g. 14 = 2 * 7 = 7 * 2. So I used a while loop to pop all identical ugly number in candidate list.\n```\ndef nthSuperUglyNumber(n, primes):\n\tcand = [(p, p, 1) for p in primes]\n\tugly = [1]\n\tfor _ in range(n-1):\n\t\tugly.append(cand[0][0])\n\t\twhile cand[0][0] == ugly[-1]:\n\t\t\tx, p, i = heapq.heappop(cand)\n\t\t\theapq.heappush(cand, (p*ugly[i], p, i+1))\n\treturn ugly[-1]\n```\nSo the time complexity is O(n * logk) where k is the size of primes. Its efficiency is lit when k is large.
[]