$$\color{Red}{第k个数-三种语言代码}$$

我的网站=> 分享了我关于前后端的各种知识和生活美食~

我于Acwing平台分享的零散刷的各种各样的题

题目介绍

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

输入格式
第一行包含两个整数 n 和 k。

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

输出格式

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

数据范围

1 ≤ n ≤ 100000

1 ≤ k ≤ n

输入样例：

5 3
2 4 1 5 3

输出样例：

3

java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 100010, n, k;
    static int[] a = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int quick_sort(int l, int r, int k, int [] a) {
        if (l >= r) return a[l];
        int x = a[l + r >> 1], i = l - 1, j = r + 1;
        while(i < j){
            while (a[++i] < x);
            while (a[--j] > x);
            if (i < j){
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        if (j >= k) return quick_sort(l, j, k, a);
        else return quick_sort(j + 1, r, k - j + 1, a);
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        k = Integer.parseInt(s1[1]);
        String[] s2 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(s2[i]);
        System.out.println(quick_sort(0, n-1, k, a));
    }
}

Python3 代码

def quick_sort(a, l, r, k):
    if l >= r: return a[l]
    i , j, x = l-1, r+1, a[(l+r) // 2]
    while i < j:
        while 1:
            i += 1
            if a[i] >= x:
                break
        while 1:
            j -= 1
            if a[j] <= x:
                break
        if i < j:
            a[i], a[j] = a[j], a[i]

    if j - l + 1 >= k:
        return quick_sort(a, l, j, k)
    else:
        return quick_sort(a, j+1, r, k - (j - l + 1))

if __name__ == '__main__':
    n, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    print(quick_sort(a, 0, n-1, k))

C++代码

#include <iostream>
using namespace std;
const int N = 100010;

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;
}