プログラマー-走りきれなかった選手、k個

完走していない選手

質問する

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

せいげんじょうけん

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

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

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

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

I/O例
participant
completion
return
["leo", "kiki", "eden"]
["eden", "kiki"]
"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]
["josipa", "filipa", "marina", "nikola"]
"vinko"
["mislav", "stanko", "mislav", "ana"]
["stanko", "ana", "mislav"]
"mislav"

問題を解く

参加者の配列にある限り、配列にない要素を完了します.
简単だと思いましたが、长い时间がかかりました.私の知らない問題でも構いません.
次は私が問題を解く方法です.

	1차 시도 : 배열 반복문 2개 : 실행 시간 최악 13
	2차 시도 : 배열 반복문 2개 + boolean 배열 1개 : 실행 시간 최악 13
	3차 시도 : ArrayList 2개 + boolean 배열 1개 : 실행 시간 최악 9
	4차 시도 : ArrayList 2개 : 실행 시간 최악 9 ~ 12
	5차 시도 : ArrayList 1개 : 실행 시간 최악 8
	6차 시도 : ArrayList 1개 + break문 추가 : 실행 시간 최악 6
	7차 시도 : HashMap 1개 + ArrayList 1개 : 실행 시간 최악 7
	8차 시도 : HashMap 1개 : 실행 시간 최악 1초, 효율성 + 정확도 100점
	==> 8차 시도에는 방법을 아예 바꿔서 Key : String, Value : Count로 표현했다. 
	==> 그 다음 completion 배열과 비교하며 값이 있는 경우 1개씩 지워나갔다.
	==> 최종적으로 남는 단 하나의 HashMap을 출력하면 됐다.

中間のboolean配列を使用する理由は、boolean配列のtrue、falseのみをチェックし、参加者配列のインデックスなどの正解にエクスポートするためです.HashMapという資料構造を用いた.Mapは、KeyとValueからなる資料構造である.KeyはMapの中で唯一でなければならない.つまり、繰り返してはいけません.HashMapの使用方法とほぼ同じ資料構造にHashTableがあるそうです.2つのクラスの違いは、Threadの観点から安全なのか、それとも安全ではなく速度が速いのかということです.
安全な資料構造はHashTableであり、迅速な資料構造はHashMapである.HashMap輸入はjava.util.Map及びjava.util.HashMapを使用する.
次は解題コードです.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {

        Map<String, Integer> par = new HashMap();
        for(int i = 0; i < participant.length; i++) {
            if(par.containsKey(participant[i])) {
                int count = (int) par.get(participant[i]);
                par.put(participant[i], count + 1);
            }
            else
                par.put(participant[i], 1);
        }
        
        for(String i : completion) 
            if(par.containsKey(i)) {
                if(par.get(i) == 1)
                    par.remove(i);
                else  // 동명이인이 2명 이상 있는 경우
                    par.put(i, par.get(i) - 1);
            }
        
        String answer = "";
        for(String key : par.keySet()) 
            answer = key;
        
        return answer;
    }
}

HashMapの中で、肝心なのは選手の名前、価値を数えて、何人の選手がいるかを覚えることです.そして,完成配列では,選手たちの名前が資料構造にあるかどうかをチェックし,countを減らす方法を用いた.結局一人しか残っていません.

k番目の数

質問する

問題の説明
配列のi番からj番までを切り取って並べ替えると、k番目の数字を求めようとします.
例えばarrayが[1,5,2,6,3,7,4],i=2,j=5,k=3の場合
arrayの2番目から5番目の場合は[5,2,6,3].
1の配列を並べ替えると[2,3,5,6].
2からの配列の3番目の数字は5です.
配列配列、[i、j、k]を要素とする2次元配列コマンドをパラメータとして与える場合は、commandsのすべての要素に前述の演算を適用した結果を配列に戻してsolution関数を作成します.

せいげんじょうけん

arrayの長さは100を超えない.

arrayの各要素は1または100未満です.

コマンドの長さは50を超えません.

コマンドの各要素の長さは3です.

I/O例
arrays
commands
return
[1, 5, 2, 6, 3, 7, 4]
[[2, 5, 3], [4, 4, 1], [1, 7, 3]]
[5, 6, 3]

問題を解く

この問題は,まず配列を切り取ってから,切り取った配列を並べ替える問題である.解題コードを見てください.

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        int i = 0;
        for(int[] arr : commands) {
            int[] temp = Arrays.copyOfRange(array, arr[0] - 1, arr[1]);
            Arrays.sort(temp);
            answer[i] = temp[arr[2] - 1];
            i++;
        }
        
        return answer;
    }
}

上から見るとArrays類を使用しています.solutionメソッドとして与えられたパラメータの配列をtempに切り取る.このとき,配列を裁断する際にはArraysクラスのcopyOfRangeメソッドを用いた.copyOfRange(array, start, end)のように使用すると、配列配列は最初から最後まで-1が裁断方法です.次いで、Arrays.sortによって裁断された配列が並べ替えられる.
私が最初にこの問題をしたときはArrays.sortを使わず、選択順位を体現しました.(クイックソートがはっきり覚えていません)