UVa 11462

UVa 11462

題目

http://domen111.github.io/UVa-Easy-Viewer/?11462

有多筆測試資料,每筆測試資料第一行有一個正整數 $n$,接下來有 $n$ 個數字

這 $n$ 個數字保證都在 $1$ ~ $100$ 之間

請將這些數字排序後輸出

想法

最單純的想法就是直接排序後輸出

可以直接使用 C++ STL sort

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, arr[2000010];
int main(){
while(cin>>n && n){
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
for(int i=0 ; i<n ; i++){
if(i) cout<<" ";
cout<<arr[i];
}
cout<<"\n";
}
return 0;
}

時間複雜度分析

輸入時間複雜度為 $O(n)$

排序時間複雜度為 $O(nlogn)$

輸出時間複雜度為 $O(n)$

總時間複雜度約為 $O(2n + nlogn)$

想法 2

因為已知數字的範圍,而且範圍不大

我們可以直接使用陣列紀錄每個數字出現的次數,再統計過後輸出即可,甚至不需要排序

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, arr[2000010], age[110];
bool out=false;
int main(){
while(cin>>n && n){
// 先初始化 age 陣列
for(int i=0 ; i<=100 ; i++){
age[i]=0;
}
for(int i=0 ; i<n ; i++){
cin>>arr[i];
// 統計
age[arr[i]]++;
}
for(int i=1 ; i<=100 ; i++){
if(age[i] > 0){
for(int j=0 ; j<age[i] ; j++){
if(out) cout<<" ";
else out=true;
cout<<i;
}
}
}
cout<<"\n";
}
return 0;
}

時間複雜度分析

輸入時間複雜度為 $O(n)$

統計時間複雜度為 $O(n)$

輸出時間複雜度為 $O(n)$

總時間複雜度約為 $O(3n)$