hackerrank新年カオスコードの最適化

Question

私はHackerranksの「新年カオス」問題のために私のソリューションを最適化しようとしています。問題の要点は次のようになります（問題hereへのリンク）：1からnまでのn人のキューがあり、それぞれの人が自分の前に直接賄賂をかけて場所を交換し、キュー（この場合、リスト/配列のインデックス0）。それぞれの人は最大2回しか賄賂を取ることができません（すでに賄賂を贈った人に賄賂を贈ることはできません）。賄賂がすべて払われた後、あなたはその人の秩序が与えられ、あなたの仕事は、その時点までにいくつの賄賂が取られたのかを判断することです。例えば、あなたが[3,2,1]を与えられた場合、答えは3つの賄賂（賄賂を贈られた人1と2と賄賂を贈られた人1）です。私の解決策は、各人のために、私よりも大きいラベルを持っている私の左の人の数を数えることでした（彼らは彼らの左に行くために人に賄賂を払わなければならなかったでしょう）。 （わずかに）事を複雑にするために、与えられたテストケースのうちのいくつかは、誰かが2回以上の贈り物をした場合にのみ可能です（すなわち、[4,1,2,3] - 4人の賄賂を受けた人3、次に2人、フロント）。このような場合は、単に「あまりにも混乱します」と出力してください。とにかく、ここのコードです：

# n is the number of people in the list 
# q is the order of the people after the bribery has taken place ex. [1, 3, 2, 5, 4] 

for i in range(1, n + 1): # for each person i in the list 
    index = q.index(i) 
    if i - index > 3: # more than two bribes 
     bribes = "Too chaotic" 
     break 
    for j in range(index): # for each number to the left of i, if greater than i, count it as a bribe 
     if q[j] > i: 
      bribes = bribes + 1 
print bribes 

私の問題は、大きなテストケースの一部とアウトコード時間は（あなたが唯一の各テストケースを実行するために多くの時間を与えられている）ということです。アルゴリズムをタイムアウトしないように最適化するにはどうすればよいですか？この問題を別の言語で試してみるべきですか？

ご協力いただきありがとうございます。

Answer 1

コードには2つの問題があります。

まず、指定された配列を末尾から最初に反復する必要があります。その理由は、最初から反復する場合は、内部ループ内の配列全体を反復処理する必要があるからです。しかし、最後の要素から反復する場合は、逆数を数えるために各数字の左の2つの数字をチェックするだけです。私は、これがあなたのコードが大規模なテストケースで "タイムアウト"する理由だと思います。

最後に、賄賂を最後の行にプリントアウトするときは、外側のループから逸脱したかどうかを確認するか、i == nで終了してください。それ以外の場合は、 "Too chaotic"と既に計算した賄賂が印刷されることがあります。