网站开发直播,商标网注册查询官网,投资者关系互动平台,东方网站建设题目#xff1a; 写一个程序来找第 n 个超级丑数。超级丑数的定义是正整数并且所有的质数因子都在所给定的一个大小为 k 的质数集合内。比如给你 4 个质数的集合 [2, 7, 13, 19], 那么 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 是前 12 个超级丑数。注意事项#xff1a;… 题目 写一个程序来找第 n 个超级丑数。超级丑数的定义是正整数并且所有的质数因子都在所给定的一个大小为 k 的质数集合内。比如给你 4 个质数的集合 [2, 7, 13, 19], 那么 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 是前 12 个超级丑数。注意事项 永远都是超级丑数不管给的质数集合是什么。给你的质数集合已经按照升序排列。0 k ≤ 100, 0 n ≤ 10^6, 0 primes[i] 1000样例 给出 n 6 和质数集合 [2, 7, 13, 19]。第 6 个超级丑数为 13所以返回 13 作为结果。 思路 丑数产生的规律除了第一个数字其余所有数字都是之前已有数字乘以任意一个在质数数组里的质数得到。point数组需要好好想想。 参考答案 class Solution {
public:/** param n: a positive integer* param primes: the given prime list* return: the nth super ugly number*/int nthSuperUglyNumber(int n, vectorint primes) {// write your code hereint len primes.size();vectorint point(len,0);//用于保存当前的位置这个需要仔细想想vectorint ugly(n,INT32_MAX);//不要用INT16_MAX,有些测试用例过不了ugly[0] 1;for(int i1; in; i){for(int j0; jlen; j){ugly[i] min(ugly[i],ugly[point[j]]*primes[j]);}for(int j0; jlen; j){if(ugly[i] ugly[point[j]]*primes[j]){point[j];}}}return ugly[n-1];}
};
