c508 - 去蟲
題目描述
題目給定一個長度為 N 的整數序列，要求先將序列從小到大排序後輸出。接著，從排序後的序列中移除重複的元素，並以降序輸出剩餘的唯一元素。
解題思路
本題的解題思路主要分為兩個步驟：
- 排序： 使用
std::sort函數將輸入的序列從小到大排序。 - 去重並反向輸出： 遍歷排序後的序列，使用一個變數
t記錄上一個輸出過的元素。如果當前元素不等於t，則輸出該元素，並更新t。這樣可以確保只輸出唯一的元素，且輸出順序為降序。
複雜度分析
- 時間複雜度: O(n log n)
- 排序部分使用
std::sort，時間複雜度為 O(n log n)。 - 去重和輸出部分遍歷序列一次，時間複雜度為 O(n)。
- 因此，整體時間複雜度為 O(n log n)。
- 排序部分使用
- 空間複雜度: O(1)
- 除了輸入序列外，只使用了常數個額外變數，因此空間複雜度為 O(1)。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
#include <algorithm>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0){
putchar_unlocked('0');
return;
}
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int a[100001];
int main(){
int n,t=-1;
n=read();
for(int i=0;i<n;++i)
a[i]=read();
std::sort(a,a+n);
for(int i=0;i<n;++i){
write(a[i]);
putchar_unlocked(' ');
}
putchar_unlocked('\n');
for(int i=n-1;i>=0;--i){
if(t!=a[i]){
write(a[i]);
putchar_unlocked(' ');
t=a[i];
}
}
}