思路：只要牽扯到排序，那么復(fù)雜度就是O(nlogn)的了。這里我們借鑒了快速排序的思想，首先任取一個(gè)數(shù)字，將小于它的放到左邊，大于它的放到右邊，然后這個(gè)數(shù)字的位置就可以確定。通過(guò)比較k和這個(gè)數(shù)字的位置，我們就可以判斷應(yīng)該在這個(gè)數(shù)字的左邊還是右邊，然后就可以重復(fù)上面的操作。最終復(fù)雜度是O(n)，但是最終數(shù)組的位置會(huì)改變。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e6+100; int a[maxx]; int n,k;inline int dfs(int l,int r) {if(l<r){int i=l,j=r;int x=a[l];while(i!=j){while(i<j&&a[j]>x) j--;while(i<j&&a[i]<=x) i++;if(i<j) swap(a[i],a[j]);}a[l]=a[i];a[i]=x;return i;} } inline int find(int len,int num) {int l=0;int r=len-1;int res=dfs(l,r);while(res!=num){if(res>num) {r=res-1;res=dfs(l,r);}else {l=res+1;res=dfs(l,r);}}return a[num]; } int main() {scanf("%d%d",&n,&k);for(int i=0;i<n;i++) scanf("%d",&a[i]);printf("%d\n",find(n,n-k));return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的O(n)算法得到数组中第k大的数字的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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