寻找第k大数(快排思想)
发布时间:2020-12-14 03:54:28 所属栏目:大数据 来源:网络整理
导读:剔除了相同的数,快排是从小到大排序的,所以k做了处理。 #include iostream#include cstdiousing namespace std;int hash[20000005]={0};int A[10000005];int counter=0;int k;int partition(int *A,int l,int r){ int x=A[r]; int i,j; int temp; i=l-1; f
剔除了相同的数,快排是从小到大排序的,所以k做了处理。 #include <iostream> #include <cstdio> using namespace std; int hash[20000005]={0}; int A[10000005]; int counter=0; int k; int partition(int *A,int l,int r) { int x=A[r]; int i,j; int temp; i=l-1; for (j=l;j<=r-1;j++) if (A[j]<=x && j!=i) { i=i+1; temp=A[j]; A[j]=A[i]; A[i]=temp; } temp=A[i+1]; A[i+1]=A[r]; A[r]=temp; return i+1; } int quick_sort(int *A,int r) { int mid; mid=partition(A,l,r); if (mid==k-1) return A[mid]; else if (mid>k-1) return quick_sort(A,mid-1); else return quick_sort(A,mid+1,r); } int main() { int n; scanf("%d%d",&n,&k); int i; int a; for (i=0;i<=n-1;i++) { scanf("%d",&a); if (!hash[a+10000000]) { hash[a+10000000]=1; A[counter++]=a; } } k=counter-k+1; printf("%dn",quick_sort(A,counter-1)); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |