【leetcode刷题】T47-超级丑数
【英文题目】（学习英语的同时，更能理解题意哟~）
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 = , primes = [,,,]
Output:
Explanation: [,,,,,,,,,,,] is the sequence of the first
super ugly numbers given primes = [,,,] of size 4.
Note:
1is a super ugly number for any givenprimes.- The given numbers in
primesare 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* 个超级丑数。
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
示例:
输入: n = , primes = [,,,]
输出:
解释: 给定长度为 的质数列表 primes = [,,,]，前 个超级丑数序列为：[,,,,,,,,,,,] 。
说明:
1是任何给定primes的超级丑数。- 给定
primes中的数字以升序排列。 - 0 <
k≤ 100, 0 <n≤ 106, 0 <primes[i]< 1000 。 - 第
n个超级丑数确保在 32 位有符整数范围内。
【思路】
本题可直接参照【T46-丑数 II】方法三。当primes为[2, 3, 5]时，新增元素为min(ls[i2]*2, ls[i3]*3, ls[i5]*5)，其中ls[i2]*2、ls[i3]*3以及ls[i5]*5都恰好大于ls最后一个元素。
【代码】
python版本
class Solution(object):
def nthSuperUglyNumber(self, n, primes):
"""
:type n: int
:type primes: List[int]
:rtype: int
"""
index = [] * len(primes)
ls = []
while len(ls) < n:
min0 = sys.maxsize
for i in range(len(primes)):
while ls[index[i]] * primes[i] <= ls[-1]:
index[i] +=
min0 = min(min0, ls[index[i]] * primes[i])
ls.append(min0)
return ls[-1]
C++版本
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
int count = ;
vector<int> ls(,);
vector<int> index(primes.size(), );
int min0;
for(int count=; count<n; count++){
min0 = INT_MAX;
for(int i=; i<primes.size(); i++){
while(ls[index[i]] * primes[i] <= ls[ls.size()-1])
index[i]++;
min0 = min(min0, ls[index[i]] * primes[i]);
}
ls.push_back(min0);
}
return ls[ls.size()-1];
}
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-04-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
