プログラマーが完走していない選手

完走していない選手
問題の説明
多くのマラソン選手がマラソンに参加した.1人の選手を除いて、すべての選手がマラソンを完走した.
マラソンに出場する選手の名前と完走した選手の名前の並びが完成したら、完走していない選手の名前を返す解決関数を書いてください.
せいげんじょうけん

マラソンに出場する選手は1人以上10万人以下.

完了長さは参加者長1より小さい.

参加者の名前は20文字を超えない.

の参加者には同名の人がいる可能性があります.

I/O例
participantcompletionreturn["leo", "kiki", "eden"]["eden", "kiki"]"leo"["marina", "josipa", "nikola", "vinko", "filipa"]["josipa", "filipa", "marina", "nikola"]"vinko"["mislav", "stanko", "mislav", "ana"]["stanko", "ana", "mislav"]"mislav"
I/O例説明

例#1
「leo」は参加者名簿に載っているが、フルコースを走る者名簿には載っていないため、フルコースを完走できなかった.

例#2
「vinko」は参加者名簿に載っていたが、完走者名簿に載っていなかったため完走できなかった.

例#3
「誤導」は参加者リストに2人いたが、完走者リストには1人しかいなかったため、1人は完走しなかった.

concept
初めてこの問題に触れたとき.
小分類の解詩を見て、ディック・シャナリーを利用したいです.
ただし、所定のI/Oの例によれば…
参加者の名前だけでハッシュする場合、同じ名前の人はハッシュ競合をどのように処理するか分かりません...(同名の異人を所定の配列の順序で区別できる場合は.列挙して一意の鍵として保存する…)
与えられた条件をもっと細かく見る.
完走者の長さは参加者より1つ小さくなければならない.
この条件を見て、簡単に考えてみることにしました.
参加者と完走者をソートした後...最初から比較して、完走していない人を見つければいいです.
->この場合...完走しなかった人が並んだ最後に...(ソートの時間的複雑さはO(logn)…)最悪の場合O(n)時間が必要です...一定時間で見つける方法は...ないみたい...
code

# 완주하지 못한 선수
def solution(participant, completion):
    participant.sort()
    completion.sort()
    num = len(completion)
    for i in range(num):
        if(participant[i] != completion[i]):
            return participant[i]
    answer = participant[num]
    return answer

リファレンス
他にも答えが書かれていて、他の人の解答を参考にすることができます...最も効果的な解答は、参加者のすべてのハッシュ値を加算し、コメント者のすべてのハッシュ値を減算することです.完全な距離を走っていないハッシュ値のプールを探しています...