f675 - FJCU_109_Winter_Day2_Lab3 二元搜尋樹
題目描述
題目要求讀取 N 個介於 1 到 100 之間的數字，將這些數字由小到大排序後輸出，然後判斷一個給定的數字 q 是否存在於這 N 個數字中，並輸出 "Yes" 或 "No"。雖然題目名稱是二元搜尋樹，但實際上程式碼並未建立二元搜尋樹。
解題思路
程式碼使用了一個大小為 101 的整數陣列 a 作為雜湊表，用於記錄輸入的數字。陣列的索引代表數字本身，陣列的值 1 表示該數字存在。程式首先讀取 N 個數字，並將對應陣列位置的值設為 1。然後，程式遍歷陣列，將存在（值為 1）的索引（數字）從小到大輸出。最後，程式檢查數字 q 是否在陣列中存在，如果存在則輸出 "Yes"，否則輸出 "No"。
複雜度分析
- 時間複雜度: O(N + 100) (N 是輸入數字的數量，100 是陣列的大小。遍歷輸入數字 O(N)，遍歷陣列輸出 O(100))
- 空間複雜度: O(101) (使用固定大小的陣列，空間複雜度為常數)
程式碼
#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>
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');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int a[101];
int main(){
int n=read(),x;
while(n--){
x=read();
a[x]=1;
}
x=read();
for(int i=0;i<101;++i){
if(a[i]){
write(i);
putchar_unlocked('\n');
}
}
if(a[x]){
putchar_unlocked('Y');
putchar_unlocked('e');
putchar_unlocked('s');
}
else{
putchar_unlocked('N');
putchar_unlocked('o');
}
}