力扣HOT100 - 215. 数组中第K个最大元素

news/2024/11/13 9:07:25/

解题思路:

快速选择,目标是找出数组中第 k 小(或第 k 大)的元素,而不是对整个数组进行排序。

(需要和快排进行区分,快排的目的是排序)

注意:

i = l - 1, j = r + 1; 为什么要这么写?而不是 i = l; j = r ?

因为是先执行do语句的内容,一开始进循环就已经先i++或者j--了,所以进循环前需要-1和+1。

java">class Solution {public int findKthLargest(int[] nums, int k) {int n = nums.length;return quickselect(nums, 0, n - 1, n - k);}public int quickselect(int[] nums, int l, int r, int k) {if (l == r) return nums[k];int i = l - 1, j = r + 1;while (i < j) {do i++; while (nums[i] < nums[l]);do j--; while (nums[j] > nums[l]);if (i < j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}if (k <= j) return quickselect(nums, l, j, k);else return quickselect(nums, j + 1, r, k);}
}


http://www.ppmy.cn/news/1461991.html

相关文章

深度学习中常见的九种交叉验证方法汇总

目录 1. K折交叉验证&#xff08;K-fold cross-validation&#xff09; 2. 分层K折交叉验证&#xff08;Stratified K-fold cross-validation&#xff09; 3. 时间序列交叉验证&#xff08;Time Series Split&#xff09; 4. 留一交叉验证&#xff08;Leave-One-Out Cross-…

SAP BSEG VS ACDOCA 差异

温习一下 ACDOCA VS BSEG matinal&#xff1a;S4 HANA 详解ACDOCA与BSEG的区别都在这了_sap acdoca-CSDN博客

神经网络案例实战

&#x1f50e;我们通过一个案例详细使用PyTorch实战 &#xff0c;案例背景&#xff1a;你创办了一家手机公司&#xff0c;不知道如何估算手机产品的价格。为了解决这个问题&#xff0c;收集了多家公司的手机销售数据&#xff1a;这些数据维度可以包括RAM、存储容量、屏幕尺寸、…

汇昌联信科技:做拼多多网店要押金吗?

做拼多多网店要押金吗?”这个问题&#xff0c;其实与拼多多的平台规则有关。在开店之前&#xff0c;商家需要详细了解平台的各项规定和费用构成&#xff0c;这样才能做好充足的准备。 一、明确回答问题 做拼多多网店&#xff0c;不需要支付押金。拼多多的入驻门槛相对较低&…

Python学习之路 | Python基础语法(一)

数据类型 Python3 中常见的数据类型有&#xff1a; Number&#xff08;数字&#xff09;String&#xff08;字符串&#xff09;bool&#xff08;布尔类型&#xff09;List&#xff08;列表&#xff09;Tuple&#xff08;元组&#xff09;Set&#xff08;集合&#xff09;Dict…

Python 自动化脚本系列:第3集

21. 使用 cryptography 自动化文件加密 Python 的 cryptography 库提供了一种安全的方式&#xff0c;使用对称加密算法对文件进行加密和解密。你可以自动化加密和解密文件的过程来保护敏感数据。 示例&#xff1a;文件加密和解密 假设你想使用对称加密算法加密一个文件&…

linux系统介绍和安装教程(含安装链接放在最下面了)

一、linux系统简介 在Linux和C语言的发展历程中&#xff0c;有几位关键人物为它们的诞生和推广做出了重要贡献。 首先&#xff0c;肯汤姆森&#xff08;Ken Thompson&#xff09;是一位在AT&T公司工作的员工&#xff0c;他不仅发明了B语言&#xff0c;还创造了Unix系统。…

AIGC行业现在适合进入吗

人工智能、物联网、基因编辑和量子计算等新兴技术领域正在以前所未有的速度发展&#xff0c;这些技术的结合正在重塑我们的世界。在这个充满机遇和挑战的时代&#xff0c;AIGC&#xff08;人工智能、基因编辑和量子计算&#xff09;行业备受关注&#xff0c;许多人都在考虑是否…