Leetcode215_数组中的第K个最大元素

devtools/2024/9/24 21:17:22/

1.leetcode原题链接:. - 力扣(LeetCode)

2.题目描述

给定整数数组 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

3.实现方法

方法一:基于快排

           在分区的过程当中,我们会对子数组进行划分,如果需要的下标正好就是划分得到的位置(q[0]和q[1]之间) ,就直接返回 ;如果 q 比目标下标小,就递归右子区间,否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间。

快速排序:排序算法-快速排序-CSDN博客

java">class Solution {public int findKthLargest(int[] nums, int k) {if( nums.length <2){return nums[0];}return quickSort(nums,0,nums.length-1,nums.length-k);}public int quickSort(int[] arr,int l,int r,int index){if(l==r){return arr[l];}swap(arr,l+(int)(Math.random() * (r-l+1)),r);int[] p=partition(arr,l,r);if(p[0]<=index && index<=p[1]){return arr[index];}else{return p[0]<index ? quickSort(arr,p[1]+1,r,index): quickSort(arr,l,p[0]-1,index);}}public int[] partition(int[] arr, int l,int r){int small = l-1;int big =r;while(l<big){if(arr[l]<arr[r]){swap(arr,++small,l++);}else if(arr[l]>arr[r]){swap(arr,--big,l);}else{l++;}}swap(arr,big,r);return new int[]{small+1,big};}public void swap(int[] arr,int a,int b){int temp=arr[a];arr[a]=arr[b];arr[b]=temp;}}

方法二:基于堆排序

 构建一个大顶堆,做 k−1 次删除操作后堆顶元素就是要找的答案。

堆排序:排序算法-堆排序-CSDN博客

java">class Solution {public int findKthLargest(int[] nums, int k) {if( nums.length <2){return nums[0];}int heapSize=nums.length;for(int i=0;i<heapSize;i++){heapInsert(nums,i);}while(heapSize> nums.length-k+1){swap(nums,0,--heapSize);heapify(nums,0,heapSize);}return nums[0];}public void heapInsert(int[] arr,int i){while(arr[i]>arr[(i-1)/2]){swap(arr,i,(i-1)/2);i=(i-1)/2;}}public void heapify(int[] arr, int index, int heapSize){//左孩子int left = 2*index+1;//当有孩子的情况下(没有左孩子一定就没有右孩子)while(left < heapSize){//left+1 有右孩子的情况 ,比较左右孩子哪个最大int largest = left+1< heapSize && arr[left+1] >arr[left] ? left+1 :left;//判断当前节点和子节点的数谁大largest = arr[largest] >arr[index] ? largest :index;//如果最大数已经是当前数了,结束,否则与子节点交换if(largest == index){break;}swap(arr,largest,index);index =largest;left = 2*index +1;}}public void swap(int[] arr,int a,int b){int temp=arr[a];arr[a]=arr[b];arr[b]=temp;}}


http://www.ppmy.cn/devtools/7283.html

相关文章

VR全景:为户外游玩体验插上科技翅膀

随着VR全景技术的愈发成熟&#xff0c;无数人感到惊艳&#xff0c;也让各行各业看到了一片光明的发展前景。尤其是越来越多的文旅景区开始引入VR全景技术&#xff0c;相较于以往的静态风景图&#xff0c;显然现在的VR全景结合了动态图像和声音更加吸引人。 VR全景技术正在逐步改…

SSL Pinning之双向认证

双向认证处理流程 概述获取证书逆向app 获取证书的KeyStore的 key通过jadx 反编译 app 获取证书&#xff1a;frida hook 证书转换命令行转换portecle 工具使用 charles 配置 p12 格式证书 概述 本篇只介绍怎么解决ssl pinning&#xff0c; 不讲ssl/tls 原理。 为了解决ssl pinn…

一文掌握面阵相机

机器视觉应用中常见的面阵工业相机&#xff0c;其应用比较广泛&#xff0c;它主要是采用连续的、面状扫描光线来获取完成的目标图像&#xff0c;并能即使进行图像采集的相机&#xff0c;最终实现产品的检测。 面阵相机分类: 按照芯片类型&#xff1a;CCD相机和CMOS相机。 按…

Oracle数据库Bug:相关子查询多层嵌套报错:标识符无效

Oracle Bug? 一、案例描述二、解决方案<一>、升级版本<二>、改写语句 一、案例描述 在Mysql中常常有如下写法用相关子查询 order by desc limit 1来完成需求 select code,date,(select value from test t1 where t.code t1.code and t1.date between date_su…

exceljs库实现excel表样式定制化

概览 xlsx 是前端最热门的 Excel 导出方案&#xff0c;又叫做 SheetJs&#xff0c;默认不支持修改 Excel 的样式。而exceljs库就可以做到自定义excel表样式&#xff0c;下面来介绍一下其使用方法 一. 完整示例 代码示例 const exportTemplate2 () > { // 创建工作簿 …

本地启用并操作Redis

本篇文章将向各位讲解redis的基础用法&#xff0c;废话不多说我们直接开始吧&#xff01; 首先需要下载redis到你本地&#xff0c;我这儿是下载到以下文件夹中&#xff1a; 双击redis-server.exe文件运行redis&#xff1a; 然后我们另外启用一个命令窗口&#xff08;需要进入你…

Spark---核心概念(Spark,RDD,Spark的核心构成组件)详解

一、什么是Spark Spark就是一个集成离线计算&#xff0c;实时计算&#xff0c;SQL查询&#xff0c;机器学习&#xff0c;图计算为一体的通用的计算框架。 二、Spark特点 1、速度快 相比较于MR&#xff0c;官方说&#xff0c;基于内存计算spark要快mr100倍&#xff0c;基于磁…

腾讯云免费ssl证书申请与宝塔手动部署

1.在我的证书 - SSL 证书 - 控制台 (tencent.com)页面点击“申请免费证书” 2.在申请页面填写域名、邮箱&#xff0c;对于其中“验证方式”&#xff0c;如果服务器是部署在腾讯云的话&#xff0c;可以选“自动DNS” 3.等待审核通过之后&#xff0c;在我的证书 - SSL 证书 - 控…