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

質問する

質問はリンクを参照してください.

ソース

ソースは羽状バニラに置いてあります.

に答える

問題の核心は,参加者配列に存在し,完了配列に存在しない名前を見つけることである.
より容易に考えられる解法は,参加者配列中の人名を繰り返し,完了中の人名が存在するかどうかを調べることである.

質問-チェック方法

参加者配列を繰り返し、現在検索するターゲット名をAと仮定します.シナリオを繰り返し完了すると、Aという名前が表示されると、存在すると思われるかもしれませんが、実際にはそうではありません.Aという人が2人いて、そのうちの1人がマラソンを終えていないと仮定すると、この方法では問題を解くことができません.Aが最初にチェックされた後も、完了シナリオにはAという名前が含まれているからです.


▶▼▼一度はAを見つけたが、その後Aを見つけた
これらの欠点を補うために、1人を検索するたびに削除方法(空の処理方法)を使用できます.

質問-時間の複雑さ

しかし、この方法にも欠点がある.時間の複雑さ
参加者の鍵がnであると仮定すると、完了はn−1である.したがって、計算時間の複雑さ
O (n * (n - 1)) = O (n^2)
二乗時間の複雑さは通常悪いアルゴリズムに分類されるので,他の方法を考えた.チェック完了スキームの時間的複雑度がO(1)である場合、アルゴリズムは以下の時間的複雑度を有する可能性がある.
O (n * 1) = O (n)

改善：適切なリソース構造を選択

クエリには、時間的複雑度O(1)を持つデータ型がいくつかあります.例えば、ArrayListを問い合わせる場合の時間的複雑度はO(1)であり、HashMapを問い合わせる場合の時間的複雑度はO(1)である.
人名を使用してクエリーを行う場合は、時間の複雑さはO(1)でなければならないことに注意してください.ArrayListでは、valueを使用して値を検索する場合、すべての配列を1つずつ検索する必要があるため、配列のサイズがnの場合、O(n)の時間的複雑さがある.そこで、HashMapを使うことにしました.
参加者を繰り返し、マッピングに値を入力します.
名前:参加者番号(count)
つまり、Aがマラソン参加者名簿に載っていれば、Aが全部で何人参加したかを記録することになる.その後、操作を繰り返し、名前のcount数を1つずつ減算します.そうなると最終的にcountが1の人はマラソンを完走していない人です

コード#コード#

public String solution(String[] participant, String[] completion) {
    // map 에서 사용할 수 있는 공간을 넘기려는 경우 크기 확장이 일어나는데, 이 때 연산의 비용이 크므로 초기 공간을 설정해주는 것이 좋다
    // 로드팩터가 1이 아니기 때문에 1번 정도는 공간 확장이 일어날 수 있지만, 뭐 1번 정도야..
    Map<String, Integer> map = new HashMap(participant.length);

	// 참가자 count
    for (String p : participant) {
        map.put(p, map.getOrDefault(p, Integer.valueOf(0)) + 1);
    }

	// 완주자 체크
    for (String c : completion) {
        map.put(c, map.get(c) - 1);
    }

	// count 가 1인 사람이 완주하지 못한 사람
    Integer one = 1;
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        if (one.equals(entry.getValue())) {
            return entry.getKey();
        }
    }
    return null;
}