[OJ] 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]是多少?

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

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

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

至此可以看出规律, 创建长度为n的数组ugly记录前n个SUN. 创建长度为k的index数组, 其中记录着意义如上面a和b的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).