第k个数

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第 k 小数。

数据范围

1≤n≤100000

1≤k≤n

输入样例：

5 3

2 4 1 5 3

输出样例：

3

个人解析：

明显的模板题，快排之后输出第k个数,那就来复习一下快速排序的知识！

主要思想是分而治之。

算法就是：

1.在[l,r]中随机选一个数作为基准点，将整个数组分成两个子数组。

2.让这个数的左边的数都比他小，右边的数都比他大。(如果是要降序就相反)

3.递归排序左右两个子数组。

代码实现

#include<bits/stdc++.h>

const int N = 100010;

int a[N];

void quick_sort(int l,int r){

	if(l <= r) return ;

	int x = a[ (l+r) >> 1], i = l - 1, j = r + 1;

	while(i<j){ // 快排的重点

		do i++ while(a[i] > x);

		do j-- while(a[j] < x);

		if(i < j) swap(i,j);

	// 找到从左边第一个比x大的，右边第一个比x小的，如果符合范围就交换这两个出错的

	}

	quick_sort(l,j),quick_sort(j+1,r);

	// 退出循环一定是i=j，此时i(j)左边的数一定都比他小，右边的数一定都比他大

}

int main(void){

	int n,k;

	cin >> n >> k;

	for(int i=0; i < n ; ++i)   scanf("%d",&a[i]);

	quick_sort(a,0,n-1);

	printf("%d",a[k-1]);

	return 0;

}

巴特西

2022-11-01 Acwing每日一题

第k个数

个人解析：

算法就是：

代码实现

最新文章

热门文章