引用
@星丶空大佬的题解,很不错的思路,奇怪的思路+1
并没有
写一个和yxc大佬不同但差不多思想的方法,代码更简单
题目描述
给定一个长度为n的整数数列,以及一个整数k,请用快速选择算法求出数列从小到大排序后的第k个数。
样例
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整数数列。
输出格式
输出一个整数,表示数列的第k小数。
数据范围
$1≤n≤100000$,
$1≤k≤n$
输入样例:
5 3
2 4 1 5 3
输出样例:
3
算法1
(快速排序) $O(n)$
从快排的性质可以知道,每次划分区间的时候j左边的数都是小于等于x的,右边的都是大于等于x的。所以如果左区间的长度大于等于k,那么第k个数必定在左区间,所以我们只需递归左区间,反过来,如果k大于左区间长度,那么第k个数在右区间,那么相对于右区间,第k个数在右区间中变为第(k - 左区间的长度)个数,然后递归右区间即可。
时间复杂度 $O(n)$
emmm,问就是不知道怎么算的,不过肯定比 $O(nlogn)$ 小,等我看了y总的时空复杂度分析再来补吧,哈哈哈
C++ 代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n , k;
int a[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]);
}
int len = j - l + 1;
if(len >= k) return quick_sort(q , l , j , k);
else return quick_sort(q , j + 1 , r , k - len);
}
int main()
{
scanf("%d%d" , &n , &k);
for(int i = 0; i < n; ++ i) scanf("%d" , &a[i]);
int res = quick_sort(a , 0 , n - 1 , k);
printf("%d" , res);
return 0;
}
go代码
package main
import (
"fmt"
"bufio"
"os"
)
var (
n, k int
q []int
)
func quickSort(q []int, l, r, k int) int {
if(l >= r) {
return q[l]
}
i, j, x := l - 1, r + 1, q[l + ((r - l) >> 1)]
for i < j {
for {
i ++
if q[i] >= x {
break
}
}
for {
j --
if q[j] <= x {
break
}
}
if i < j {
q[i], q[j] = q[j], q[i]
}
}
len := j - l + 1
if(len >= k) {
return quickSort(q , l , j , k)
} else {
return quickSort(q , j + 1 , r , k - len)
}
}
func main() {
reader := bufio.NewReader(os.Stdin)
fmt.Fscan(reader, &n, &k)
q = make([]int, n)
for i := 0; i < n; i ++ {
fmt.Fscan(reader, &q[i])
}
res := quickSort(q, 0, n - 1, k)
fmt.Printf("%d", res)
return
}