題目鏈接：點擊查看

題目大意：給出長度為 n 的數(shù)列 a ，要求找到第 k 小的數(shù)

題目分析：因為數(shù)據(jù)給的足夠大，所以約束就是必須線性完成操作，STL 中的 nth_element() 函數(shù)可以完美實現(xiàn)操作，算是學到了一波，格式：nth_element( a.begin() , a.begin() + k , a.end() ) ，那么 a[ k ] 就是第 k + 1 小的數(shù)，完成操作后，整個序列滿足 [ 0 , k - 1 ] 的數(shù)都不大于 k ，[ k + 1 , end ] 的數(shù)都不小于 k

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=5e6+100;inline int read(){int x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = (x<<1) + (x<<3) + (ch^48);ch = getchar();}return x * f; }int a[N];int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)a[i]=read();nth_element(a+1,a+k,a+1+n);printf("%d\n",a[k]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客 - 第k小数(线性寻找第 k 小数)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。