次に大きい番号を探す
1. 序章
この記事では、同じ数字のセットを使用して、指定された非負の数よりも次に大きい数を見つけるアルゴリズムを学習します。
与えられた数がすでに与えられた数字のセットで作ることができる最大の数である場合、アルゴリズムは与えられた数自体を返す必要があります。
2. 図
まず、ソリューションのアプローチを理解しましょう。
最初に、右端の桁から指定された数値をトラバースして、右側の桁よりも小さい最初の桁を見つけます。たとえば、指定された数値が12365の場合、桁は3になります。 36。
この場合、4321のように、すべての桁が右側の桁よりも大きい場合、指定された桁のセットで可能な最大の数値であるため、指定された数値自体を返します。
数字が見つかると、の右側により大きい最小の数字が見つかります。 この例では、5<6および5>3なので、数字は5です。
次に、指定された番号の数字を交換します。 この例では、数字3と5が12365で交換され、12 5 6 3が得られます。
最後に、数字の次の数字の順序を逆にして、次に大きい数字を取得します。 この例では、シーケンス63が12563で逆になり、125 36 が得られます。これは、指定された番号12365よりも次に大きい番号です。
3. アルゴリズム
上記のアルゴリズムの擬似コードを見てみましょう。
4. 時間計算量
与えられた数の桁数を表すと仮定しましょう。
次に、アルゴリズムの最初と2番目の各ステップは、線形探索を使用して必要な桁を見つけるのに()時間がかかります。
3番目のステップは、スワップ操作を実行するために()時間を消費します。 4番目のステップでは、数字の順序を逆にするのに()時間がかかります。
したがって、上記のアルゴリズムの全体的な時間計算量は()です。
5. 結論
この記事では、最初に、同じ数字のセットを使用して、指定された非負の数よりも次に大きい数を見つけるアルゴリズムを学びました。 次に、説明したアルゴリズムの時間計算量を分析しました。