首页 > 代码库 > Leetcode 313. super ugly number
Leetcode 313. 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.
这道题和ugly number II 思路一样,关键是保留指针p,这个指针表明了下一次再乘p_i的时候应该和前面的哪一个ugly number相乘。
1 class Solution(object): 2 def nthSuperUglyNumber(self, n, primes): 3 """ 4 :type n: int 5 :type primes: List[int] 6 :rtype: int 7 """ 8 res = [1]*n 9 m = len(primes) 10 p = [-1]*m 11 v = [1]*m 12 13 for k in range(n): 14 res[k] = min(v) 15 for j in range(m): 16 if v[j] == res[k]: 17 p[j] += 1 18 v[j] = res[p[j]]*primes[j] 19 return res[-1]
Leetcode 313. super ugly number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。