f667 - FJCU_109_Winter_Day1_Lab1 第 k 大
題目描述
題目要求從一串數字中找出第 k 大的數字。輸入數字直到讀取到 -1 為止，然後讀取一個整數 k，最後輸出排序後數列中第 k 大的數字。
解題思路
這題的解題思路非常直接。首先，讀取輸入的數字，直到讀取到 -1 為止，將這些數字儲存在一個陣列中。然後，使用 std::sort 函數對陣列進行排序。最後，根據輸入的 k 值，輸出排序後陣列中對應位置的元素，即第 k 大的數字。由於題目限制數字個數不超過 100，因此陣列大小設定為 101。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是輸入數字的個數。這是因為使用了
std::sort函數，其時間複雜度通常為 O(n log n)。 - 空間複雜度: O(n)，其中 n 是輸入數字的個數。這是因為需要一個陣列來儲存輸入的數字。
程式碼
#include <stdio.h>
#include <algorithm>
using namespace std;
int a[101],it,tmp;
inline int read(){
int a(0),f(1);
char c('0');
while(c>='0'||c=='-'){
if(c=='-'){
f=-1;
c=getchar_unlocked();
}
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a*f;
}
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 main(){
while(tmp=read()){
if(tmp==-1)break;
a[it]=tmp;
++it;
}
sort(a,a+it);
tmp=read();
write(a[it-tmp]);
}