1

与えられた数の次に大きいアナグラムを見つけるための効率的なアルゴリズムは何でしょうか?

例:

  1. 入力: 7813 -> 出力: 7831
  2. 入力: 3791 -> 出力: 3917
  3. 入力: 4321 -> 出力: (なし)
4

1 に答える 1

3

基本的に、番号を右から左に移動します。減少する数字を見つけたら、停止します。その数字を前のすべての数字と比較します。次に上位の桁に置き換えてから、残りを昇順で並べ替えます。例えば：

978654321を取ります。1）数字が減少するまで、右から左に移動します。

Stop at the 7 because that is the first digit that decreases.

2）すでに見た次の最大桁を見つけます。

out of 1 2 3 4 5 6 and 8, 8 is the next largest digit to 7.

3）残りの桁を昇順で並べ替え、最後に追加します。

1234567

これは981234567を生成します

複雑：

nは桁数です。

ステップ1）O（n）。最悪の場合、数字は最後の桁まで増加する（または同じままである）ためです。

ステップ2）O（n）。最悪の場合、その数値をn桁すべてと比較する必要があるためです。

ステップ3）O（n lg n）は、ソートする必要があり、最適なソートアルゴリズムはnlgnであるためです。

したがって、このアルゴリズムはO（n lg n）で実行されます。ここでも、nは数値の桁数です。

于 2012-10-02T06:57:02.523 に答える