10989


質問する
N個の数字が与えられた場合、昇順で並べ替えられたプログラムを作成します.
入力
第1行は、数の個数N(1≦N≦1000000)を与える.2行目から、N行の数字をあげます.この数は10000以下の自然数です.
しゅつりょく
1行目からN行目まで昇順に並べた結果、1行ずつ出力されます.
に答える
試行錯誤
「うん?「これがsortの問題ではないか」ベクトル生成後にsortを回転させた結果、メモリが過剰になった.考えてみれば、int型配列が1000万個に達したら、40万バイト、これは40兆ですか?メモリが不足しています.だから考えを変えると、入力した数字は10000に達するので、入力するたびに、対応する配列のカウントを増やして出力します.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n, num;
	vector<int> arr;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num);
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());
	for (auto x : arr)
		cout << x << '\n';
}
コード#コード#
#include <iostream>
using namespace std;

int main()
{
	int n, num;
	int arr[10001] = { 0, };
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num);
		arr[num]++;
	}
	for (int i = 0; i < 10001; i++)
	{
		for (int j = 1; j <= arr[i]; j++)
			cout << i << '\n';
	}
}