更好的阅读体验
Hint:密码在本文的最下角,欢迎各位取走.
原题连接
题目描述
给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第k小数。
数据范围
1≤n≤100000
1≤k≤n
输入样例：
5 3
2 4 1 5 3
输出样例：
3
解题报告
题意理解
题意很清晰,就是让我们使用快速排序算法,求解第K小的数.
算法选择
快速排序算法,显然是我们不二选择.毕竟这是一道模板题目
欢迎各位看菜鸡我的快速排序算法的博客.
代码实现
#include <iostream>
using namespace std;
const int N = 1000010;
int q[N];
int quick_sort(int q[], int l, int r, int k)
{
if (l >= r) return q[l];
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
if (j - l + 1 >= k) return quick_sort(q, l, j, k);
else return quick_sort(q, j + 1, r, k - (j - l + 1));
}
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
cout << quick_sort(q, 0, n - 1, k) << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/39785/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
C++STL使人心情愉悦
#include <bits/stdc++.h>
using namespace std;
const int N=1000000 +1000;
int a[N],n,m,i,j,k;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
cout<<a[m];//排序快乐
return 0;
}
阅读博客密码:Acwinghh 各位不要外传哦,毕竟大家都是VIP大佬!
if (l >= r) return q[l];里面return q[k]也可以，为什么啊，这个时候k==l吗
C++STL的代码好像没有去重?
有吗
大佬，这样调用STL库函数的话算是快速排序吗？
那个sort（a +1 ）为什么数组整体可以加上一个数？
这样的a不是数组整体哦，指的是数组a的第一个元素内存地址， a+1 就会到数组a的第一个元素的下一个元素
(a[0] -> a[1])具体内容y总有在语法课指针那一章讲你好，请问如果在有重复数字的数列中输出第k小的数字，该怎么处理呢
数组去重再来吧
尝试桶排，不恶心的数据基本上2n的时间就能过
临界条件可以用 l == r 吧，找前k个不会有空集
可以
请问我的代码有什么问题吗？样例的第三四个数顺序总不对
const int N = 1e5 + 10;
int n , k , q[N];
void quick_sort( int q[] , int l , int r)
{
if( l >= r ) return ;
int x = q[l] , i = l - 1 , j = r + 1 ; if( i < j ) { do i ++ ; while( q[i] < x ); do j -- ; while( q[j] > x ); if( i < j ) swap(q[i] , q[j]); } quick_sort(q , l , j); quick_sort( q , j + 1 , r);}
int main()
{
scanf(“%d%d”, &n, &k);
for (int i = 0; i < n; i ) scanf(“%d”, &q[i]);
quick_sort( q , 0 , n- 1);
for (int j = 0; j < n; j )
printf(“\n%d”, q[k - 1]);
return 0 ;
}
while( i < j ) { do i ++ ; while( q[i] < x ); do j -- ; while( q[j] > x ); if( i < j ) swap(q[i] , q[j]); }x = q[l+r >> 1];
好像是吧
为什么不能这样写？就是把函数类型改成void，然后那个k让他在main函数中输出printf（”%d”，q[k-1]);
这样就是做了完整的快排，时间复杂度是nlogn，而实际上每次只需搜寻一边即可，满足条件用int返回，这样时间复杂度是O(n)的
大佬为什么x不能用a[(l+r)>>1]来代替？即
int quick_sort(int q[], int l, int r, int k) { if (l >= r) return q[l]; int i = l - 1, j = r + 1; while (i < j) { do i ++ ; while (q[i] < q[l + r >> 1]); do j -- ; while (q[j] > q[l + r >> 1]); if (i < j) swap(q[i], q[j]); } if (j - l + 1 >= k) return quick_sort(q, l, j, k); else return quick_sort(q, j + 1, r, k - (j - l + 1)); }l+r>>1 的位置可能会发生交换
q数组会改变的
能细说一下吗，调试了半天都是memory limit exceeded看不出什么
前面设int x = q[( l + r)/2]而不是 q[(l + r + 1)/2]就会这样
膜大佬