[LeetCode] Super Ugly Number (Medium)

时间:2021-01-05 11:26:04

Super Ugly Number

最后WA没做出来.

typedef long long int64;
#define MAXBOUND 10000000
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
bitset<MAXBOUND> bs;
int64 bound = MAXBOUND;
vector<int> v;
bs.set(1);
for (int i = 0; i < primes.size(); ++i) {
bs.set(primes[i]);
}
for (int64 i = 1; i < bound; ++i) {
if (!bs[i]) continue;
--n;
bs.set(i);
v.push_back(i);
if (n <= 0) return i;
for (int j = 0; j < v.size(); ++j) {
int64 val = v[j];
if (val >= bound / i) break;
bs.set(i * val);
}
}
return -1;
}
};

最后一个case过不了:

Input: 100000

[7,19,29,37,41,47,53,59,61,79,83,89,101,103,109,127,131,137,139,157,167,179,181,199,211,229,233,239,241,251]

Output: -1

Expected: 1092889481

bitset没法开到10^9这么大.


// @zjh08177
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> index(primes.size(), 0), ugly(n, INT_MAX);
ugly[0]=1;
for(int i=1; i<n; i++){
for(int j=0; j<primes.size(); j++) ugly[i]=min(ugly[i],ugly[index[j]]*primes[j]);
for(int j=0; j<primes.size(); j++) index[j]+=(ugly[i]==ugly[index[j]]*primes[j]);
}
return ugly[n-1];
}

思路:

假设primes=[2,3]且已经计算出了前n个SUN, 即SUN[0]SUN[n-1], 那么SUN[n]是多少?

0n-1中找到一个最小的a使得SUN[a]*2>SUN[n-1]. 同样地在0n-1中找到一个最小的b使得SUN[b]*3>SUN[n-1]. 下一个SUN一定是SUN[a]*2SUN[b]*3中较小的那个. 假设SUN[a]*2较小, 那么SUN[n]就是SUN[a]*2.

再想一步, SUN[n+1]是多少?

一定是SUN[a+1]*2SUN[b]*3中较小的那一个.

至此可以看出规律, 创建长度为n的数组ugly记录前n个SUN. 创建长度为k的index数组, 其中记录着意义如上面ab的index值.

初始时, ugly[0]=1, ugly[其他]=INT_MAX. index中元素都为0. 接下来从ugly[1]更新到ugly[n-1], 更新ugly[i] (i=1~n-1)时:

找到ugly[index[j]] * primes[j] (j=0~k-1)中最小的那个(对应的下标j记做jmin), 写入到ugly[i], 然后index[jmin]++.

最后, ugly[n-1]就是所求.

时间复杂度O(nk).

空间复杂度O(n+k).