每日一刷-Super-Ugly-Number

[每日一刷] (Super Ugly Number)

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.

Example:
Given: primes = [2, 7, 13, 19], n = 10
Return 26

解题思路

这题就是不断的选下一个最小的质数，因此可以想到用heap。
既然是一个Super Ugly的题，就用一个Super Ugly的做法吧- -

Python:

#!/usr/bin/env 
# -*- coding:utf-8 -*-
from heapq import *
class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        if n == 1:
            return 1
        length = len(primes)
        idxs = [ 0 for i in xrange(length) ]
        minLists = []
        h = []
        for i in xrange(length):
            heappush(h, [primes[i], i])
        for i in xrange(2, n):
            tup = heappop(h) # 第i-1大的数
            num, index = tup[0], tup[1]  # 第i-1大的数和index
            minLists.append([num, index])
            idx = idxs[index]
            while minLists[idx][1] > index:
                idx += 1
            nextNum = primes[index] * minLists[idx][0]
            idxs[index] = idx + 1
            heappush(h, [nextNum, index])
        return h[0][0]