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

本篇文章分享AcWing算法基础课-786第k个数-Java题解，对你有帮助的话记得收藏一下，看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 Aw786 {

	// 创建一个StreamTokenizer对象，用于读取输入流
	public static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

	// 读取下一个整数的方法
	public static int nextInt() throws IOException {
		in.nextToken();
		return (int) in.nval;
	}

	public static int n; // 数组的大小
	public static int k; // 需要找到的第k个数
	public static int[] nums; // 存储输入的数组

	public static void main(String[] args) throws IOException {
		// 读取数组的大小和需要找到的第k个数
		n = nextInt();
		k = nextInt();
		// 初始化数组
		nums = new int[n];
		// 读取数组的元素
		for (int i = 0; i < n; i++) {
			nums[i] = nextInt();
		}
		// 对数组进行快速排序
		QuickSort(nums, 0, n - 1);
		// 输出第k个数，数列中的第k个数对应数组下标为k-1
		System.out.println(nums[k - 1]);
	}

	// 快速排序算法
	public static void QuickSort(int[] a, int l, int r) {
		// 如果左边界大于或等于右边界，则直接返回
		if (l >= r) {
			return;
		}
		// 初始化左右指针和基准值
		int i = l - 1, j = r + 1, x = a[l + r >> 1];
		// 进行分区操作
		while (i < j) {
			do {
				i++;
			} while (a[i] < x); // 找到左边大于等于基准值的元素
			do {
				j--;
			} while (a[j] > x); // 找到右边小于等于基准值的元素
			if (i < j) {
				// 交换这两个元素
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		// 递归地对左右两个分区进行快速排序
		QuickSort(a, l, j);
		QuickSort(a, j + 1, r);
	}

}

🔗参考

• https://www.acwing.com/problem/content/description/788/
• https://blog.csdn.net/coder_heweilai/article/details/141720984

作者：程序员何未来-heweilai.com

---

🔍推荐阅读

1. AcWing算法基础课-785快速排序-Java题解
2. 【七夕节实践】把爱心代码放在自己的网站上是什么体验？
3. 塑造你的技术名片：写给程序员的个人品牌建设指南

欢迎关注我的博客：@程序员何未来，持续为你输出有价值的技术文章~
你们的点赞👍 收藏⭐ 留言🗨️ 关注✅
是我持续创作，输出优质内容的最大动力！谢谢！

文章关键词：算法，计算机算法，算法题解，算法竞赛，Java，数据结构，AcWing算法基础课

文章来源:https://blog.csdn.net/coder_heweilai/article/details/141816402
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！