[leetcode] 313. Super Ugly Number

[leetcode] 313. Super ugly Number

Description

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.

Example:

Input:

n = 12, primes = [2,7,13,19]

Output:

32

Explanation:

[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 is a super ugly number for any given primes.The given numbers in primes are in ascending order.0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

分析

题目的意思是：求一个数的第n个超级丑数。

由于不知道质数的个数，可以用一个idx数组来保存当前的位置，然后我们从每个子链中取出一个数，找出其中最小值，然后更新idx数组对应位置，注意有可能最小值不止一个，要更新所有最小值的位置。

代码

class Solution {public: int nthSuperUglyNumber(int n, vector& primes) { vector dp(n,INT_MAX); vector count(primes.size(),0); dp[0]=1; for(int i=1;i

参考文献

​​[LeetCode] Super Ugly Number 超级丑陋数​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。