水平|2751:ソート番号2(Java)

問題に関する詳細は、白駿|2751号:数列2において入手可能である.

に答える

ArrayList入力Collectionssort()を使用しました.
Collections.sort()は、混合ソートアルゴリズムと呼ばれる挿入、合成ソートを組み合わせた方法を採用する.
Collections.sort()は、時間的複雑度保証O(n)~O(nlogn)を表す.
アレイを作成し、Arraysを実行します.sort()を使用しなかった理由は以下の通りです.Arrays.sort()最悪の場合の時間複雑度はO(n)である²)そうですから.
でも上の方法で解いた後、他の解答を探してみたら、全く思いつかなかった方法を見つけて、とても悲しかったです.重複した入力がないので,配列のindexを用いて時間的複雑度をO(n)と解くことができるとは思わなかった.
入力された数値制御値は1000000以下であるため、20000001の長さの配列を生成することができる.
0はarr[1000]に格納される構造である.

ソースコード

Collections.sort()の使用

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}

		Collections.sort(list);

		for (int i = 0; i < n; i++) {
			bw.write(String.valueOf(list.get(i)) + "\n");	
		}
		
		br.close();
		bw.close();
	}

}

配列内のインデックスの使用

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		boolean[] arr = new boolean[2000001];

		for (int i = 0; i < n; i++) {
			arr[Integer.parseInt(br.readLine()) + 1000000] = true;
		}

		for (int i = 0; i < arr.length; i++) {
			if (arr[i]) {
				bw.write(String.valueOf(i - 1000000) + "\n");
			}
		}

		br.close();
		bw.close();
	}

}

メモリ、時間

Collections.sort()の使用
メモリ:172544 KB
時間:1816ミリ秒
配列内のインデックスの使用
メモリ:142008 KB
時間:960ミリ秒