您的位置:首页 > 汽车 > 时评 > 妇科医生咨询在线咨询免费_洛阳网站制作_疫情最新消息今天公布_sem和seo是什么职业

妇科医生咨询在线咨询免费_洛阳网站制作_疫情最新消息今天公布_sem和seo是什么职业

2025/4/6 6:04:48 来源:https://blog.csdn.net/weixin_60205306/article/details/146921507  浏览:    关键词:妇科医生咨询在线咨询免费_洛阳网站制作_疫情最新消息今天公布_sem和seo是什么职业
妇科医生咨询在线咨询免费_洛阳网站制作_疫情最新消息今天公布_sem和seo是什么职业

题目描述 

215. 数组中的第K个最大元素https://leetcode.cn/problems/kth-largest-element-in-an-array/

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 10 

 快速排序背景

基本思想:分治法
排序过程:在数组中随机选取一个元素值作为中间值,然后对数组分区,使所有比中间值小的数据移动到数组左侧,使所有比中间值大的数据移动到数组右侧;

然后对左右两侧递归处理 使得子数组中只有一个数字为止。

 快速排序代码

public class Quick_Sort {/*** 快速排序思想* 1、随机选取数组中的一个数组作为中间值* 2、利用双指针  P1 P2 P1从-1下标位置,P2从0下标位置* 3、如果P2下标位置当前值小于 中间值 移动P1指针 交换P1 P2指针下的数组值* 4、P2扫描数组至最后一个位置 移动P1指针和P2指针下的值交换*/public int[] sortArray(int[] nums) {//调用快速排序quicksort(nums, 0, nums.length - 1);return nums;}/*** 快速排序递归处理* 基本思想:分治法,连续处理数组将其连续缩小范围处理 直到子数组中只剩下一个值** @param nums* @param start* @param end*/public void quicksort(int[] nums, int start, int end) {if (end > start) {int pivot = partition(nums, start, end);quicksort(nums, start, pivot - 1);quicksort(nums, pivot + 1, end);}}/*** 分区函数** @param nums* @param start:分区处理的第一个下标位置* @param end:分区处理数组的最后下标位置* @return:返回处理后的中间值的下标*/public int partition(int[] nums, int start, int end) {// 获取下标随机值int random = new Random().nextInt(end - start + 1) + start;// 随机值int randomNum = nums[random];//将随机值和最后一个元素交换swap(nums, random, end);//创建双指针int P1 = start - 1;//遍历数组for (int P2 = start; P2 <= end; P2++) {//1、第一个逻辑 如果P2指针的元素值小于随机元素值 交换if (nums[P2] < randomNum) {P1++;//交换P2与P1的值swap(nums, P1, P2);}}P1++;swap(nums, P1, end);return P1;}private void swap(int[] nums, int i, int j) {if (i != j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}}

leetcode题目解题思路

因为题目中要找的是第k大的数字,那我们可以拿一个数组来模拟

* [3,2,1,5,6,4], k = 2 
* [1,2,3,4,5,6] 寻找的目标值就是5 对应的数组下标为 nums.length - k = 6 - 2 = 4

如果使用快速排序的分区思路,只要不断缩小分区,之后寻找中间值的数组下标为4的数组值就可以:

解释一下:

因为分区之后 nums.length - k 数组左边部分 比这个之小 右边部分比这个值大 即使数组不是完全排序的,中间值也是第k大的数字

 

class Solution {public int findKthLargest(int[] nums, int k) {int target = nums.length - k;int start = 0;int end = nums.length - 1;//分区查找中间值int index = partition(nums, start, end);while (index != target) {if (index > target) {//如果中间值下标大于目标值下标 则 目标值在左侧end = index - 1;} else {//如果中间值小标小于目标值下标 则 目标值在右侧start = index + 1;}//再次查找中间值index = partition(nums, start, end);}//返回目标值return nums[index];}/*** 分区函数** @param nums* @param start:分区处理的第一个下标位置* @param end:分区处理数组的最后下标位置* @return:返回处理后的中间值的下标*/public int partition(int[] nums, int start, int end) {// 获取下标随机值int random = new Random().nextInt(end - start + 1) + start;// 随机值int randomNum = nums[random];//将随机值和最后一个元素交换swap(nums, random, end);//创建双指针int P1 = start - 1;//遍历数组for (int P2 = start; P2 <= end; P2++) {//1、第一个逻辑 如果P2指针的元素值小于随机元素值 交换if (nums[P2] < randomNum) {P1++;//交换P2与P1的值swap(nums, P1, P2);}}P1++;swap(nums, P1, end);return P1;}private void swap(int[] nums, int i, int j) {if (i != j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com