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
| #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
| #include<iostream> #include<algorithm> using namespace std; int n, arr[2000010], age[110]; bool out=false; int main(){ while(cin>>n && n){ 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)$