コード戦争のトレーニング中に、ジョセフ順列に関する課題に出くわしました。最初に紙の上で解決し、後でそれをコードに変換しようとしました。
問題は次のとおりです。
私の主なアイデアは次のとおりです。
- 応答を保持するための補助配列を用意する
2 つの反復子を使用します。
- i: 指定された配列の現在のインデックスを追跡する
- k: 順列のステップを追跡する
i を 0 に、k を 1 に初期化する
- 元の配列に 1 つの要素しか残っていない場合:
- 要素を出力配列にプッシュする
- i が配列の最後のインデックスでない場合:
- k = ステップの場合:
- 元の配列から要素を取り出し、出力配列にプッシュし、最後に k = 1 を置き換えます
- k != ステップの場合:
- i と k をインクリメントする
- k = ステップの場合:
- i が元の配列の最後のインデックスである場合 (および配列に複数の要素がある場合):
- k = ステップの場合:
- 元の配列から要素を取り出し、それを出力配列にプッシュし、k = 1 を置き換えて i = 0 に設定します
- k != ステップの場合:
- i = 0 に設定し、k をインクリメントします
- k = ステップの場合:
function josephus(items,step){
var output = [];
var i = 0;
var k = 1;
if( items == [] ) {
return [];
}
while (items.length != 1) {
if (k == step && i == items.length - 1) {
output.push(items[i]);
items.splice(i, 1);
i = 0;
k = 1;
} else if (k == step && i != items.length - 1) {
output.push(items[i]);
items.splice(i, 1);
k = 1
} else if (k < step && i == items.length - 1) {
k++;
i=0;
} else if (k < step && i != items.length - 1) {
k++;
i++;
}
}
output.push(items[0]);
return output;
}
これは機能しますが、効率的ではありません。実行サンプル テストで実行すると、5 つのサンプル テストに合格したことがわかりますが、STDERR: Execution Timed Out (12000 ms) も含まれています。
サンプル テストは次のとおりです。
Test.assertSimilar(josephus([1,2,3,4,5,6,7,8,9,10],1),[1,2,3,4,5,6,7,8,9,10])
Test.assertSimilar(josephus([1,2,3,4,5,6,7,8,9,10],2),[2, 4, 6, 8, 10, 3, 7, 1, 9, 5])
Test.assertSimilar(josephus(["C","o","d","e","W","a","r","s"],4),['e', 's', 'W', 'o', 'C', 'd', 'r', 'a'])
Test.assertSimilar(josephus([1,2,3,4,5,6,7],3),[3, 6, 2, 7, 5, 1, 4])
Test.assertSimilar(josephus([],3),[])
私の質問は、どうすればこれをより効率的にできるでしょうか?
私が使用しているアルゴリズムが間違っているのでしょうか、それとも実装ですか?
コメントには、次の 2 つのことが記載されていました。
push() は非常に遅いです。これは私の可能性の 1 つでした (間違ったデータ構造)
再帰を見ることを提案しました（これは、アルゴリズムについての私の疑問にさらにつながります）。ただし、これを再帰的にする方法は実際にはわかりません。
よろしくお願いします。