カウントソートの実装はPythonで

Question

私はこれを試していますHackerRank problem。これまでのところ、このコードは次のようになりました。

n = int(raw_input()) 
ar = [] 

for i in xrange(n): 
    ar.append(raw_input().split()) 

output = [0] * 1000000 
count = [0] * 100 

for a in ar:  
    count[int(a[0])] += 1 

total = 0 

for a in xrange(100): 
    old = count[a] 
    count[a] = total 
    total += old 

for a in ar: 
    if ar.index(a) < n/2: 
     output[count[int(a[0])]] = '-' 
    else: 
     output[count[int(a[0])]] = a[1] 
    count[int(a[0])] += 1 

for o in output: 
    if type(o) != str: 
     break 
    else: 
     print o, 

5つのテストケースのうち、1つしか通過しませんでした。 2は実行時間が長いためタイムアウトしましたが、それは今は私の優先事項ではありません。私の優先事項は、完全に失敗した他の2つのテストケースに合格しています。私はどこに間違っていたのかわかりません。私はおそらく私のコードをより効率的にすることができるのは分かっていますが、今は正しい出力を得ることに集中しています。

Answer 1

私はすべての問題（時間と正確さの両方）がar.index(a)を使用して値が入力リストの前半にあるかどうかを確認していると思われます。

この行は常に非常に遅くなります（リストの検索にはO（N）時間がかかります）。入力の最初の半分に2行、入力の前半に1行、後半になる。代わりに、あなたがリストを反復処理しているとして、インデックスを取得するためにenumerateを使用します。

for i, a in enumerate(ar): 
    if i < n/2: 
     output[count[int(a[0])]] = '-' 
    else: 
     output[count[int(a[0])]] = a[1] 
    count[int(a[0])] += 1 

あなたはおそらく（output長nを作る、または一度だけintに各キーの変換のような）いくつかの他のものを改善しますが、取得することができますおそらくlist.index()への呼び出しを取り除くことが最も重要な修正です。