题目描述
给定一个长度为n的整数数列,以及一个整数k,请用快速选择算法求出数列从小到大排序后的第k个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整数数列。
输出格式
输出一个整数,表示数列的第k小数。
数据范围
1≤n≤100000,
1≤k≤n
输入样例:
5 3
2 4 1 5 3
输出样例:
3
观众老爷们,如果本思路对您有帮助,求关注一波~~~
思路:
由于是找第K个数,所以我们的关点第主要是找从0号位置找第k个点,所以在有限的区间内,要传参l, r, k
1.先找中间位置的值x,通过快排,让左边的所有数都<= x, 右边的数都>=x
2.统计左边 <=x 的个数s
2.1 如果 s 的个数 >= k, 很明显,第k个小的数在l, j的左边 quickSort(l, r, k)
2.2 如果 s 的个数 < k, 那么第k个小的数在j+1, r的区间中
注意,因为k的左边有s个数在j+1的左边区间中,为了找第k个值,则需要更新 k = k - s
quickSort(j+1, r, k - s)
int quick_sort(int l, int r, int k){
if(l >= r) return q[l];
int x = q[l];
int i = l - 1, j = 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 s1 = j - l + 1;
if(k <= s1) return quick_sort(l, j, k);
return quick_sort(j + 1, r, k - s1);
java 代码
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] q = new int[N];
static int n, k;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
for(int i = 0; i < n; i ++) q[i] = sc.nextInt();
int res = quickSort(0, n - 1, k);
System.out.println(res);
}
private static int quickSort(int l, int r, int k){
if(l >= r) return q[l];
int x = q[l + r >> 1], i = l - 1, j = r + 1;
while(i < j){
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
if(i < j){
int tmp = q[i];
q[i] = q[j];
q[j] = tmp;
}
}
int s1 = j - l + 1;
if(k <= s1) return quickSort(l, j, k);
return quickSort(j + 1, r, k - s1);
}
}
python3 代码
def quickSort(q, l, r, k):
if(l >= r): return q[l]
x = q[l + r >> 1]
i = l - 1
j = r + 1
while i < j:
while True:
i += 1
if q[i] >= x:
break
while True:
j -= 1
if q[j] <= x:
break
if i < j:
tmp = q[i]
q[i] = q[j]
q[j] = tmp
s1 = j - l + 1
if(k <= s1): return quickSort(q, l, j, k)
else:
return quickSort(q, j + 1, r, k - s1)
def main():
c = list(map(int, input().split()))
n = c[0]
k = c[1]
q = list(map(int, input().split()))
# print(' '.join(list(map(str, q))))
res = quickSort(q, 0, n - 1, k)
print(res)
main()
c++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n, k;
int q[N];
//改进,依据当前x的左边都是<=x 右边都是>=x
//处理第k个数是在轴心点x左边的n(n>=k)个数的第k个还是在右边第k-num(leftCount(l 到 轴心点)) 当前仅当轴心点左边的个数 < k
int quick_sort(int l, int r, int k){
if(l >= r) return q[l];
int x = q[l + r >> 1];
int i = l - 1, j = 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 s1 = j - l + 1;
if(k <= s1) return quick_sort(l, j, k);
return quick_sort(j + 1, r, k - s1);
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i ++) cin >> q[i];
//quick_sort(q, 0, n - 1);
cout << quick_sort(0, n - 1, k) << endl;
return 0;
}