プログラマー-完走しなかった選手

1.質問

質問リンク
質問する
多くのマラソン選手がマラソンに参加した.1人の選手を除いて、すべての選手がマラソンを完走した.
マラソンに出場する選手の名前と完走した選手の名前の並びが完成したら、完走していない選手の名前を返す解決関数を書いてください.
せいげんじょうけん
1.マラソンに出場する選手は1名以上100000名以下である.
2.完了長さが参加者の長さ1より小さい.
3.参加者の名前は、少なくとも1つまたは20つの小文字で構成される.
4.参加者の中に同名の人がいる可能性があります.
I/O例

I/O例説明
例1
「leo」は参加者名簿に載っているが、フルコースを走る者名簿には載っていないため、フルコースを完走できなかった.
例2
「vinko」は参加者名簿に載っていたが、完走者名簿に載っていなかったため完走できなかった.
例#3
「誤導」は参加者リストに2人いたが、完走者リストには1人しかいなかったため、1人は完走しなかった.

2.解答

2-1. 条件

の参加者の中には同名の人がいるかもしれません.

2-2. に答える

いろいろな方法があります.
1つ目の方法は,参加者と完走者をソートすることである.
要素を順番に比較する場合、他の値があれば、その値は正しいのではないでしょうか.
もちろんこの答えも通じます.
nlogn(ソート)の時間的複雑さのため,文字列の比較効率も高くない.
あまりお勧めしたくないです.
第2の方法は地図資料構造を利用することである.
上記の条件によると、参加者の中には同名の人がいる.
mapをmap<参加者名、参加者数>として定義します.
そして,完走者を巡回し,地図上の参加者数を1つ減らす.
最後にmapに参加者数が0より大きい要素がある場合、
その要素は完走できなかった選手になるのでしょうか?
この方法.
mapに加工し、
巡視が終わったら、参加者数を1つ下げて、n、
mapをn回遍歴し,正解を見つける必要があるため,全時間複雑度はO(n)である.
再整理すると.
1.参加者配列をmap<参加者名、参加者数>に加工します.
2.完走したチームを巡回し、mapの参加者名に対応する参加者数を1に減らす.
3.mapを巡回し、参加者数が0より大きい要素の名前を返します.

3.完全なコード

function solution(participant, completion) {
    // 1. 참가자 배열을 map<참가자 이름, 참가자 수> 로 가공합니다.
    participant = participant.reduce((m, name) => {
        m[name] = m[name] || 0;
        m[name]++;
        return m;
    }, {});

    // 2. 완주자 배열을 순회하며 map의 참가자 이름에 해당하는 참가자 수를 1씩 낮춰줍니다.
    completion.forEach(name => participant[name]--);

    // 3. map을 순회하며 참가자 수가 0보다 큰 요소의 이름을 반환합니다.
    return Object.entries(participant).find(([_, count]) => count)[0];
}