丑数とは、2, 3, 5のいずれかの数の積からなる数のことです。

最初、私は深さ優先探索（DFS）と集合（set）を使って解こうとしたが、これは効率的ではありませんでした。代わりに、各丑数を順番に配置したいと考えました。例えば、6の次は8であり、9ではありません。

次の丑数は以下の3つの可能性のうちの最小値になります：

prev1 * 2;
prev2 * 3;
prev3 * 5;

ここで、prev1, prev2, prev3は異なる数である可能性があります。それぞれが大きすぎたり小さすぎたりしないように調整しながら、常に最小値を選択します。

具体的な例を見てみましょう。最初の丑数は1で、次に考えられる数は以下の通りです：

1 * 2 = 2;
1 * 3 = 3;
1 * 5 = 5;

これらの中で最小の2を選択し、次は以下のようになります：

2 * 2 = 4;
1 * 3 = 3;
1 * 5 = 5;

ここで3を選択します。次は以下のようになります：

2 * 2 = 4;
2 * 3 = 6;
1 * 5 = 5;

次は4を選択します。次は以下のようになります：

3 * 2 = 6;
2 * 3 = 6;
1 * 5 = 5;

次は5を選択します。次は以下のようになります：

3 * 2 = 6;
2 * 3 = 6;
2 * 5 = 10;

次は6を選択しますが、6は2つあるため、prev2とprev3を同時に増加させます。

このようにして、3つのポインタを利用して丑数を求めることができます。

コード例1

class UglyNumberFinder {
public:
    int findNthUglyNumber(int n) {
        std::vector<int> uglyNumbers(n + 1);
        uglyNumbers[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        for (int i = 1; i < n; ++i) {
            int next2 = uglyNumbers[index2] * 2;
            int next3 = uglyNumbers[index3] * 3;
            int next5 = uglyNumbers[index5] * 5;
            int nextUgly = std::min({next2, next3, next5});
            uglyNumbers[i] = nextUgly;
            if (next2 == nextUgly) ++index2;
            if (next3 == nextUgly) ++index3;
            if (next5 == nextUgly) ++index5;
        }
        return uglyNumbers[n - 1];
    }
};

コード例2: 貪欲法と優先度付きキュー

ここでは、最小値を取り出し、それに2, 3, 5を掛けて新たな丑数を生成し、それを優先度付きキューに入れるという手法を使用します。

#include <queue>
#include <unordered_set>

class UglyNumberFinder {
public:
    int findNthUglyNumber(int n) {
        std::priority_queue<long long, std::vector&lt;long long&gt;, std::greater&lt;&gt;&gt; pq;
        std::unordered_set&lt;int&gt; seen;
        pq.push(1);
        int count = 0;
        long long current = 1;
        while (count < n) {
            current = pq.top();
            pq.pop();
            if (!seen.count(current)) {
                seen.insert(current);
                pq.push(current * 2);
                pq.push(current * 3);
                pq.push(current * 5);
                ++count;
            }
        }
        return current;
    }
};</code>

この方法では、重複を避けるためにハッシュセットを使用しています。