algo-aha

丑数

• https://leetcode.com/problems/ugly-number-ii/

int nthUglyNumber(int n) {
    // 每个因子x对应一个要相乘的已知丑数seq[ix]，以生成下个丑数 min{ seq[ix]*x }
    // 当生成了下个丑数后，所有参与生成的因子的索引ix++
    vector<int> seq;
    seq.push_back(1);
    int i2 = 0, i3 = 0, i5 = 0;
    for (int i = 1; i < n; i++) {
        int next = min({ seq[i2] * 2, seq[i3] * 3, seq[i5] * 5 });
        seq.push_back(next);
        if (next == seq[i2] * 2) i2++;
        if (next == seq[i3] * 3) i3++;
        if (next == seq[i5] * 5) i5++;
    }
    return seq.back();
}

超级丑数

• https://leetcode.com/problems/super-ugly-number

上面算法的扩展

int nthSuperUglyNumber(int n, vector<int>& primes) {
    vector<int> seq;
    seq.push_back(1);
    // 每个因子对应有一个要相乘的已知丑数，以生成下个丑数
    // 第j个因子primes[j]对应的丑数是seq[idx[j]]
    const int M = primes.size();
    vector<int> idx(M, 0); 
    for (int i = 1; i < n; i++) {
        int next = INT_MAX;
        for (int j = 0; j < M; j++) {
            next = min(next, seq[idx[j]] * primes[j]);
        }
        seq.push_back(next);
        for (int j = 0; j < M; j++) {
            if (next == seq[idx[j]] * primes[j]) idx[j]++;
        }
    }
    return seq.back();
}

注意：丑数可以无限生成下去，因此不是在行列有序的矩阵中找第k小数的问题。