LintCode Q518 Super Ugly Number in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年11月3日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import heapq
class Solution:
# @param {int} n a positive integer
# @param {int[]} primes the given prime list
# @return {int} the nth super ugly number
def nthSuperUglyNumber(self, n, primes):
# Write your code here
times = [0]*len(primes) # initialize primes counter
ugly = [1] # initialize ugly number list
min_heap = [(primes[i], i) for i in xrange(len(primes))] # initialize minial heap
heapq.heapify(min_heap)
while(len(ugly) < n):
# step 1: get minimal number and prime index from min_heap
(min_num, ind) = heapq.heappop(min_heap)
# step 2: count prime frequency
times[ind] += 1
# step 3: add min_num to ugly number list
if ugly[-1] != min_num:
ugly.append(min_num)
# step 4: add new num to min_heap
heapq.heappush(min_heap, (primes[ind] * ugly[times[ind]], ind))
return ugly[-1]
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。