[標準C++]配列10989個数3
7731 ワード
質問する
N個の数字が与えられた場合、昇順で並べ替えられたプログラムを作成します.
入力
第1行は、数の個数N(1≦N≦1000000)を与える.2行目からN行に付与する.この数は10000以下の自然数です.
しゅつりょく
1行目からN行目まで昇順に並べた結果、1行ずつ出力されます.
https://www.acmicpc.net/problem/10989
最初のメモリ制限は、不注意でメモリが超過したためです.入力値は最大10^7個まで可能で、int型データにすべて入れると4 byeごとに40 mbになります.
通常、時間の複雑さを計算しますが、この問題の重点は空間の制限です.
<イニシャルコード>
#define _CRT_SECURE_NO_WARNINGS //scanf오류 없앰
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int n, *arr;
scanf("%d", &n);
arr = new int[n];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
sort(arr, arr + n);
for (int i = 0; i < n; i++) {
printf("%d\n", arr[i]);
}
}次に、入力した最大値が10000の点を示します.
10000個の配列を生成した後、入力値をその配列の値にすべて加算します.
時間制限は5秒で、10000+nを繰り返しても時間を超えません.
<修正コード>
#define _CRT_SECURE_NO_WARNINGS //scanf오류 없앰
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int n, temp;
int arr[10001] = {0}; //초기화를 해줘야 정상적으로출력
scanf("%d", &n);
while (n--) {
scanf("%d", &temp);
arr[temp] += 1;
}
for (int i = 1; i <= 10000; i++) {
while (arr[i] > 0) {
printf("%d\n", i);
arr[i] -= 1;
}
}
}Reference
この問題について([標準C++]配列10989個数3), 我々は、より多くの情報をここで見つけました https://velog.io/@cldhfleks2/10989テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol