白駿18870題

質問:座標の圧縮

問題の説明:

垂直線上のN個の座標X 1,X 2,...,XNがあります。この座標に座標圧縮を適用します。Xiを座標圧縮した後、X'iの値はXi>Xjを満たす異なる座標の個数に等しくなければならない。X1, X2, ..., XNに座標圧縮を適用すると、X"1,X"2,...,X'Nを印刷します。

コード:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main_18870 {
    public static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int[] cnt= new int[N];
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }


        int same=0;

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(i!=j && arr[i]>arr[j]){
                    for(int k=0;k<j;k++){
                        if(arr[j]==arr[k]) same++;
                    }
                    if(same==0) cnt[i]++;
                    same=0;
                }
            }
        }
        for(int i=0;i<N;i++){
            System.out.print(cnt[i] +" ");
        }
    }
}

このように三重for文に初めてアクセスするのは当然タイムアウトであり、検索方法はhashmapであるが、これもタイムアウトの結果であり、StringBuilderの使用が必要であることがわかったので再度アクセスする。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main_18870 {
    public static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int[] arrclone = new int[N];
        int cnt=0;
        HashMap map = new HashMap<>();
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        arrclone = arr.clone();
        Arrays.sort(arrclone);
        for(int i=0;i<N;i++){
            if(!map.containsKey(arrclone[i])) map.put(arrclone[i],cnt++);
        }
        for (int i = 0; i < arr.length; i++) {
            sb.append(map.get(arr[i])).append(" ");
        }
        System.out.println(sb);
    }
}

質問:

クローンアレイをもう1つ作成し、アレイをコピーしてソートします。

for(int i=0;i<N;i++){
            if(!map.containsKey(arrclone[i])) map.put(arrclone[i],cnt++);
        }

次に、上記のコードのように、各配列の値をキー値とし、繰り返さない場合はcnt++でカウントします。簡単に言えば、昇順に並べ替えた後、対応する値ごとに等号を記入し、最小の値は0で、次いで1であり、このように等号を記入する。