当前位置: 首页 > ai >正文

LCR 076. 数组中的第 K 个最大元素

一、题目描述

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

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

示例 1:

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

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

提示:

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

二、题目解析

1、插入排序

class Solution {public int findKthLargest(int[] nums, int k) {insertSort(nums);return nums[k - 1];}public void insertSort(int[] nums) {for(int i = 1;i < nums.length;i++){int target = nums[i];int j = i - 1;;for(;j >= 0;j--){if(nums[j] < target){nums[j+1] = nums[j];}else{//找到第一个大于待排元素的元素break;}            }//注意此处不能为nums[j+1] = nums[i],因为在交换过程中nums[i]被改变nums[j+1] = target;}}
}

2、快速排序思想1(一次扫描交换一个到目标位置)
左指针指向i=0,待排元素,(循环遍历前存储待排元素)
右指针指向j=length-1,最后一个元素。
从j位置往前遍历,找到大于待排元素,把该元素换到左指针指向位置(此时右指针位置废弃);
从i位置往后遍历,找到小于待排元素,把该元素换到右指针指向位置(上轮的废弃位置;且此时左指针位置废弃,下一轮遍历将交换到该位置);
再从j位置往前遍历,以此类推。
在此过程中,i走过的区域都是大于等于待排元素的,j走过的区域都是小于待排元素的,最后i和j相遇且指向的都是废弃元素。直接把待排元素排到这里即可。

class Solution {public int findKthLargest(int[] nums, int k) {quickSort(nums,0,nums.length - 1);return nums[k-1];}public void quickSort(int[] nums,int start,int end){//递归结束条件if(start >= end){return;}int mid = (start + end) / 2;swap(nums,start,mid);int index = partition(nums,start,end);quickSort(nums,start,index - 1);quickSort(nums,index + 1,end);}public int partition(int[] nums,int start,int end) {int i = start,j = end;int target = nums[start];while(i < j){while(nums[j] < target && i < j){j--;}nums[i] = nums[j];while(nums[i] >= target && i < j){i++;}nums[j] = nums[i];}//最后return i或者j位置上的元素都可以,因为打破while的时候i==jnums[j] = target;return j;}public void swap(int[] nums,int i,int j){int temp = nums[j];nums[j] = nums[i];nums[i] = temp;}
}

在这里插入图片描述
3、快速排序思想2(一次扫描交换两个到目标位置)

http://www.xdnf.cn/news/17881.html

相关文章:

  • 集成电路学习:什么是Image Segmentation图像分割
  • QT|windwos桌面端应用程序开发,当连接多个显示器的时候,如何获取屏幕编号?
  • 嵌入式第二十九课!!!回收子进程资源空间函数与exec函数
  • Deepoc具身智能模型如何重塑康复辅助设备
  • 如何理解AP中SM中宿主进程?
  • 另类的pdb恢复方式
  • 第十四节:物理引擎集成:Cannon.js入门
  • python自学笔记9 Seaborn可视化
  • 【100页PPT】数字化转型集团信息化总体解决方案(附下载方式)
  • 【机器人-基础知识】ROS1和ROS2对比
  • shell脚本实现sha256sum校验并拷贝校验通过的文件
  • OpenCV Python——图像查找(特征匹配 + 单应性矩阵)
  • Kotlin作用域函数全解:run/with/apply/let/also与this/it的魔法对决
  • fs模块_写入文件
  • Layers(图层)
  • OpenSCA开源社区每日安全漏洞及投毒情报资讯|14th Aug. , 2025
  • 【车联网kafka】常用参数及其命令总结(第八篇)
  • Backblaze 2025 Q2硬盘故障率报告解读
  • Web攻防-大模型应用LLM安全提示词注入不安全输出代码注入直接间接数据投毒
  • CAXA电子图板2026(国产CAD之光)
  • C# 中的 string / StringBuilder / 值类型 / 引用类型 / CLR 总结
  • Design Compiler:使用IC Compiler II Link
  • Tasking编译问题: E207: syntax error - token “<integer>“ delete的解决方案
  • 【机器学习】核心分类及详细介绍
  • 电视同轴电缆全面指南:从基础到应用,批量测量一键计量
  • 【博客系统测试报告】---web界面自动化测试
  • 使用PyTorch实现手写数字识别系统:从理论到实践
  • 附045.Kubernetes_v1.33.2高可用部署架构二
  • 介绍大根堆小根堆
  • C++——分布式