313.Super Ugly Number

Tags: [heap]

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

Write a program to find the nthsuper ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime listprimesof sizek. For example,[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]is the sequence of the first 12 super ugly numbers givenprimes=[2, 7, 13, 19]of size 4.

Note:
(1)1is a super ugly number for any givenprimes.
(2) The given numbers inprimesare 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.

Time Limited Exceeded:

class Solution(object):

    class Node(object):
        def __init__(self, val, ugly_num_index, prime):
            self.val = val
            self.ugly_num_index = ugly_num_index
            self.prime = prime

        def __cmp__(self, other):
            if not isinstance(other, self.__class__):
                raise ValueError('Cannot compare with two different type objs')

            return self.val - other.val


    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        if not n or not primes:
            raise ValueError('the input is invalid')

        # using these given primes to build ugly numbers.
        # build min heap based on given primes.
        min_heap = []
        for prime in primes:
            min_heap.append(self.Node(prime, 0, prime))
        heapq.heapify(min_heap)

        # generate ugly numbers one by one.
        ugly_nums = [0 for _ in xrange(n)]
        ugly_nums[0] = 1
        for i in xrange(1, n):
            min_val_node = heapq.heappop(min_heap)
            ugly_nums[i] = min_val_node.val

            # update the val for curr min_val_node
            min_val_node.val = ugly_nums[min_val_node.ugly_num_index + 1] * min_val_node.prime
            min_val_node.ugly_num_index += 1
            heapq.heappush(min_heap, min_val_node)

            # try to make the top node's val of min_heap is greater than the ugly_nums[i]
            while min_heap and min_heap[0].val == ugly_nums[i]:
                node = heapq.heappop(min_heap)
                node.val = ugly_nums[node.ugly_num_index + 1] * node.prime
                node.ugly_num_index += 1
                heapq.heappush(min_heap, node)

        return ugly_nums[n - 1]

Revelation:

• Didn't understand the above algorithm.