問題タブ [josephus]

コード戦争のトレーニング中に、ジョセフ順列に関する課題に出くわしました。最初に紙の上で解決し、後でそれをコードに変換しようとしました。

問題は次のとおりです。

私の主なアイデアは次のとおりです。

• 応答を保持するための補助配列を用意する

• 2 つの反復子を使用します。

  • i: 指定された配列の現在のインデックスを追跡する
  • k: 順列のステップを追跡する

• i を 0 に、k を 1 に初期化する

• 元の配列に 1 つの要素しか残っていない場合:
  • 要素を出力配列にプッシュする
• i が配列の最後のインデックスでない場合:
  • k = ステップの場合:
    • 元の配列から要素を取り出し、出力配列にプッシュし、最後に k = 1 を置き換えます
  • k != ステップの場合:
    • i と k をインクリメントする
• i が元の配列の最後のインデックスである場合 (および配列に複数の要素がある場合):
  • k = ステップの場合:
    • 元の配列から要素を取り出し、それを出力配列にプッシュし、k = 1 を置き換えて i = 0 に設定します
  • k != ステップの場合:
    • i = 0 に設定し、k をインクリメントします

これは機能しますが、効率的ではありません。実行サンプル テストで実行すると、5 つのサンプル テストに合格したことがわかりますが、STDERR: Execution Timed Out (12000 ms) も含まれています。

サンプル テストは次のとおりです。

私の質問は、どうすればこれをより効率的にできるでしょうか?

私が使用しているアルゴリズムが間違っているのでしょうか、それとも実装ですか?

コメントには、次の 2 つのことが記載されていました。

• push() は非常に遅いです。これは私の可能性の 1 つでした (間違ったデータ構造)

• 再帰を見ることを提案しました（これは、アルゴリズムについての私の疑問にさらにつながります）。ただし、これを再帰的にする方法は実際にはわかりません。

よろしくお願いします。