AcWing算法基础课-786第k个数-Java题解

大家好，我是何未来，本篇文章给大家讲解《AcWing算法基础课》786 题——第 k 个数。本篇文章详细解析了如何使用 Java 实现快速排序算法，以解决查找数组中第 k 个元素的问题。通过深入浅出的讲解，展示了从输入读取到快速排序实现的完整流程，帮助读者理解并掌握这一经典算法的核心思想和应用技巧。

❓题目描述

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤100000,
1≤k≤n

输入样例：

5 3
2 4 1 5 3

输出样例：

3

💡算法思路

1. 对数列进行快速排序
2. 找出排序后数列中的第 k 个数

具体实现步骤：

• 调用QuickSort方法对数组nums进行快速排序。
• 快速排序的核心思想是选择一个基准值，将数组分为两部分，一部分小于基准值，一部分大于基准值，然后递归地对这两部分进行排序。
• 在QuickSort方法中，首先选择一个基准值（这里选择的是中间位置的值），然后使用两个指针i和j从数组的两端向中间移动，分别找到第一个大于基准值和小于基准值的元素，并交换它们的位置，以此来分区。
• 递归地对基准值左右两部分进行快速排序，直到整个数组有序。
• 排序完成后，直接输出数组中第 k-1 位置的元素，即第 k 个数。

✅Java代码

package basic.sort;

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

public class