E、求第k小

题目描述

给定n(1<=n<=1000000)个元素，求第k小数(1<=k<=n)。

输入

一组样例。第一行输入两个整数n和k。第二行输入n个不同的int范围内的数。

输出

输出一行，输出第k小数。

样例输入

5 2
1 5 3 2 4

样例输出

2

题解(随机基准点算法， 分治思想)

#include<bits/stdc++.h>
#include <stdlib.h> 
#include <time.h>  
using namespace std;

const int t = 1000000;
int s[t];

// 产生随机整数 
int random(int begin,int end)
{
    srand((unsigned)time(NULL));
    return rand()%(end - begin + 1) + begin;
}

// 将小于基点的放在基点左侧，大于的放在右侧 
int Partition(int a[], int p, int r){
	int i=p;
	int j=r+1;
	int x = a[p];
	while(1){
		while(a[++i]<x && i<r);
		while(a[--j] > x);
		if(i>=j) break;
		swap(a[i], a[j]);
	}
	a[p] = a[j];
	a[j] = x;
	return j; // 返回排序后基点序号 
}
// 随机选择基准点 
int RandomizedPartition(int a[], int p, int r){
	int i = random(p, r);
	swap(a[i], a[p]);
	return Partition(a, p, r); 
} 

int RandomizedSelect(int a[], int p, int r, int k){
	if(p==r) return a[p];
	int i= RandomizedPartition(a, p, r);
	int j = i - p + 1; // 在基点左侧的数的个数 
	if(k <= j) return RandomizedSelect(a, p, i, k);  // 在基点的左侧找 
	else return RandomizedSelect(a, i+1, r, k-j); // 在基点右侧的 找第k-j小 
}

int main(){
	int n,k,sum=0;
	cin>>n>>k;
	for(int i=0; i<n; i++) cin>>s[i];	
	sum = RandomizedSelect(s, 0, n-1, k);
	cout<<sum;
	return 0;
}