第k大的数(快速排序的划分过程) - c++编程基础

TOP

第k大的数(快速排序的划分过程)

2015-07-20 17:42:10 来源: 作者: 【大中小】浏览:1次

Tags：快速排序划分过程

瑶瑶的第K大

Time Limit: 10000/5000MS ( Java/Others)Memory Limit: 512000/256000KB (Java/Others) SubmitStatisticNext Problem

Problem Description

一天，萌萌的妹子--瑶瑶(tsyao)很无聊，就来找你玩。可是你们都不知道玩什么。。。尴尬了一阵子，机智的瑶瑶就提议：“这样吧，你说N个整数xi，然后在随意说一个数字k，我能够快速地说出这些数字里面第 k 大的数字。”

Input

第1行两个整数N, K以空格隔开；

第2行有N个整数（可出现相同数字，均为随机生成），同样以空格隔开。

0 < n ≤ 5*10^6 , 0 < k ≤ n

1 ≤ xi ≤ 10^8

Output

输出第 k 大的数字。

Sample Input

5 2
5 4 1 3 1

Sample Output

Hint

如2，2，1中三个数字中第一大数字为2，第二大数字也为2，第三大数字为1 。

Source

tsyao

Manager

tsyao SubmitStatistic

卡我输入简直桑心病狂...

/*
* this code is made by NULL
* Problem: 1099
* Verdict: Accepted
* Submission Date: 2014-09-12 17:35:54
* Time: 3224MS
* Memory: 21212KB
*/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
              #include
              
                using namespace std; typedef long long LL; typedef unsigned long long ULL; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back #define CLR(a,x) memset(a,x,sizeof(a)) const int maxn=5e6+5; int A[maxn],n,k; int Partition(int l,int r) { if(l==r-1)return l; int q=rand()%(r-l-1)+l; swap(A[r-1],A[q]); int x=A[r-1]; int t=l-1; rep(i,l,r-2){ if(A[i]<=x){ ++t; swap(A[t],A[i]); } } swap(A[t+1],A[r-1]); return t+1; } int quick_select(int l,int r,int k) { if(l==r-1)return A[l]; int q=Partition(l,r); int Left=q-l+1; if(k==Left)return A[q]; else if(k
               
                '9')ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); while(~scanf("%d%d",&n,&k)) { srand(time(NULL)); k=n-k+1; rep(i,1,n)read(A[i]); printf("%d\n",quick_select(1,n,k)); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVA 11367 - Full Tank?(最短路+D..	下一篇：HDU 3395 Special Fish(费用流)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: