c635 - 基礎排序 #1-2 ( 位置排序 )
題目描述
題目要求讀取一行以逗號分隔的數字字串，將字串中的數字分別存入奇數位置和偶數位置的陣列中，然後分別對這兩個陣列進行排序，最後按照原始輸入的奇偶位置順序輸出排序後的數字。
解題思路
程式首先讀取輸入字串，並將其分割成數字。然後，程式將數字分別存入奇數位置和偶數位置的兩個陣列 o 和 e 中。接著，程式使用 std::sort 函數對這兩個陣列進行排序。最後，程式按照原始輸入的奇偶位置順序輸出排序後的數字。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是輸入數字的個數。這是因為
std::sort函數的時間複雜度為 O(n log n)。 - 空間複雜度: O(n)，其中 n 是輸入數字的個數。這是因為程式需要使用兩個陣列
o和e來存儲奇數位置和偶數位置的數字。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[21],it,o[21],oit,e[21],eit,tmp;
string s;
char d;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(getline(cin,s)){
tmp=eit=oit=it=0;
s+=',';
for(int i=0;i<s.length();++i){
if(s[i]>='0'&&s[i]<='9'){
tmp*=10;
tmp+=s[i]-'0';
}
else{
a[it++]=tmp;
tmp=0;
}
}
for(int i=0;i<it;++i){
if(i%2==0)
o[oit++]=a[i];
else
e[eit++]=a[i];
}
sort(o,o+oit);
sort(e,e+eit);
for(int i=0;i<it;++i){
if(i%2==0){
if(i)cout << ',';
cout << o[i/2];
}
else
cout << ',' << e[i/2];
}
cout << '\n';
}
}