数组长度为N，保证没有重复的数。 一个简单有效的方法是对数组进行排序后使用有序数组的二分查找，时间复杂度为O(NlogN)。
观察我们第一个算法，对于选定的Mid。如果数组满足a[L..Mid-1]<a[Mid]且a[Mid]<a[Mid+1..R]，即可进行区间的分割，从而使得区间范围减半。 既然如此，那么我们可以通过一次遍历交换将比a[Mid]小的数放到a[Mid]左边，比a[Mid]大的数放到a[Mid]右边。(这里使用了快速排序的思想) 其他部分仍然同有序数组的二分查找相同，但由于每一次都遍历了整个数组，所以时间复杂度变为：O(N/2^0+N/2^1+N/2^2+1)=O(2N)
#include <iostream> #include <stack> #include <cstdio> #include <cstring> #include <set> using namespace std; typedef long long ll; int main() { int n,m; scanf("%d%d",&n,&m); int yes=0,cnt=0; for(int i=1;i<=n;i++) { int t; scanf("%d",&t); if(m==t) yes=1,cnt++; else if(t<m) cnt++; } if(yes) printf("%d\n",cnt); else printf("-1\n"); }
快排思想，到K结束 #include <iostream> #include <stack> #include <cstdio> #include <cstring> #include <set> using namespace std; typedef long long ll; const int maxn=1000050; int a[maxn]; int main() { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); if(n<k) { printf("-1\n"); } else { int l=1,r=n; while(l<=r) { int flag=a[l],left=l,right=r; while(left<right) { while(left<right&&a[right]>flag) right--; a[left]=a[right]; while(left<right&&a[left]<flag) left++; a[right]=a[left]; } a[left]=flag; if(left<k) l=left+1; else if(left>k) r=left-1; else break; } printf("%d\n",a[k]); } }
