私は以下の問題に取り組んでいます。私の質問は、私の現在の実装は、Pythonで並べ替えを使用している - sorted(sorted_freq, reverse=True)
です。私は最大ヒープ(http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away/)を使用している他の実装を参照しました。私は彼らがO(n*log n)
である同じ時間の複雑さを持っていると思う(私が間違って計算した場合は、自由に修正してください)。だから私は、ソート以外のヒープを使用するパフォーマンスの面で利点があるのだろうか?ヒープを使用すると、文字列の並べ替えのパフォーマンスが向上します
私のコードはPython 2.7で書かれています。
問題:文字列と正の整数D考える
。いくつかの文字は、指定された文字列で繰り返されることがあります。同じ文字がdの距離になるように、指定された文字列の文字を並べ替えます。多くの可能な再編成が可能であり、出力は再配置の可能性があることに注意してください。そのような手配が可能でない場合は、それも報告する必要があります。 予想される時間の複雑さはです。O(n)ここで、nは入力文字列の長さです。
例:
Input: "abb", d = 2
Output: "bab"
Input: "aacbbc", d = 3
Output: "abcabc"
Input: "geeksforgeeks", d = 3
Output: egkegkesfesor
Input: "aaa", d = 2
Output: Cannot be rearranged
ソースコード:
from collections import defaultdict
def rearrange(source, distance):
freq = defaultdict(int)
for c in source:
freq[c] += 1
sorted_freq = []
for k,v in freq.items():
sorted_freq.append((v,k))
sorted_freq = sorted(sorted_freq, reverse=True)
result = [0] * len(source)
for i, (v,k) in enumerate(sorted_freq):
index = i
while index < len(result) and result[index] != 0:
index += 1
if index == len(result):
return None
count = v
while count > 0:
result[index] = k
index += distance
count -= 1
if index >= len(source) and count > 0:
return None
return result
if __name__ == "__main__":
print rearrange('abb', 2)
print rearrange('aacbbc', 3)
print rearrange('geeksforgeeks', 3)
print rearrange('aaa', 2)
niemmiのアドバイスをいただきありがとうございました。実装を検討し、リンクから参照実装と比較してください。私はループの 'for(v、k)in enumerate(sorted_freq) 'では、同じ回数のループを繰り返すので、自分のコード時間の複雑さは' O(n + m log m) (あなたの答えでは、 'n'は文字列の長さを意味し、' m'は文字列中の一意の文字数を意味します)。私があなたのコメントを間違って読んだら、私を修正してください。 –
ところで、あなたの考えを愛して、「カウンター」。 –
@LinMa:はい、一意の文字の量である外側ループ「m回」をループします。しかし、最初の 'while'ループが何回実行されるかを考えてください。私があなたに与えた例では、最初の外側ループの 'index'は' 0'に初期化され、 'result' [0]は' 0'なので '0'回実行されます。 2回目の 'index'は' 1'であり、 'result' [1]は' 0'であるのでループは '0'回実行されます。 3番目のラウンドでは、 'index'が' 2'に初期化され、 'result'の最初の空きインデックスが' 20000'であるので、より興味深いものになります。第4ラウンド 'index'は' 3'に初期化され、最初の空きインデックスは '20001'に初期化されます。 – niemmi