卖萌的弱渣

I am stupid, I am hungry.

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.

Note:

  1. 1 is a super ugly number for any given primes.
  2. The given numbers in primes are in ascending order.
  3. 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

Solution

  • priority queue 使用Python生成器和heapq.merge，将primes中各个元素的质数倍数合并在一起
(Super-Ugly-Number.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import heapq

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """

        uglies = [1]
        def gen(prime):
            for ugly in uglies:
                yield ugly * prime
        # merged: priority queue iterative
        merged = heapq.merge(*map(gen,primes))

        while len(uglies) < n:
            # current minimal value in merged, after uglies is appended.
            ugly = next(merged)
            if ugly != uglies[-1]:
                uglies.append(ugly)
        return uglies[-1]

if __name__ == "__main__":
    sol =Solution()
    sol.nthSuperUglyNumber(12,[2,3,5,7])