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

[Java·算法·中等]LeetCode215. 数组中的第K个最大元素

每天一题,防止痴呆

  • 题目
  • 示例
  • 分析思路1
  • 题解1
  • 分析思路2
  • 题解2
  • 分析思路3
  • 题解3

👉️ 力扣原文

题目

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

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

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

示例

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

分析思路1

使用优先队列堆排序(效率太差)

题解1

class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> heap = new PriorityQueue<>((n1,n2)->n1-n2);for (int n : nums){heap.add(n);}while (heap.size() > k){heap.poll();}return heap.poll();}
}

执行结果
在这里插入图片描述

分析思路2

借助Array工具类排序,然后取[数字长度-k]位元素。

题解2

class Solution {public int findKthLargest(int[] nums, int k) {Arrays.sort(nums);int n = nums.length;return nums[n-k];}
}

执行结果
在这里插入图片描述

分析思路3

采用了快速排序中的分区思想,即将一个数组分成小于某个元素和大于某个元素两部分。可以使用左右指针法进行查找。

在每次分区的过程中,通过比较当前元素与分界点的大小关系,将其移到左右两部分中。然后,对左右两部分进行递归,直到找到第N-K+1小的元素时返回结果。

题解3

public class Solution {/*** 找到数组中第K个最大元素* * @param nums 数组* @param k    第K个* @return 第K个最大元素*/public int findKthLargest(int[] nums, int k) {// 转化为第N-K+1小的元素int target = nums.length - k;int left = 0;int right = nums.length - 1;// 左右指针法查找第N-K+1小的元素while (left < right) {int pivotIndex = partition(nums, left, right);if (pivotIndex == target) {return nums[pivotIndex];} else if (pivotIndex < target) {left = pivotIndex + 1;} else {right = pivotIndex - 1;}}return nums[left];}/*** 分区,返回分区点的下标* * @param nums  数组* @param left  左下标* @param right 右下标* @return 分区点的下标*/private int partition(int[] nums, int left, int right) {int pivot = nums[right];int i = left - 1;for (int j = left; j < right; j++) {if (nums[j] <= pivot) {i++;swap(nums, i, j);}}swap(nums, i + 1, right);return i + 1;}/*** 交换数组中两个元素的位置* * @param nums 数组* @param i    位置i* @param j    位置j*/private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

执行结果
在这里插入图片描述

相关文章:

[Java·算法·中等]LeetCode215. 数组中的第K个最大元素

每天一题&#xff0c;防止痴呆题目示例分析思路1题解1分析思路2题解2分析思路3题解3&#x1f449;️ 力扣原文 题目 给定整数数组 nums 和整数 k&#xff0c;请返回数组中第 k 个最大的元素。 请注意&#xff0c;你需要找的是数组排序后的第 k 个最大的元素&#xff0c;而不…...

xgboost:算法数学原理

xgboost算法数学原理 1、求预测值 y^iϕ(xi)∑k1Kfk(xi),fk∈F,(1)\hat{y}_i\phi\left(\mathbf{x}_i\right)\sum_{k1}^K f_k\left(\mathbf{x}_i\right), \quad f_k \in \mathcal{F},\tag{1} y^​i​ϕ(xi​)k1∑K​fk​(xi​),fk​∈F,(1) F{f(x)wq(x)}(q:Rm→T,w∈RT)\mathca…...

map、multimap、unordered_map

引用&#xff1a;windows程序员面试指南 map map 红黑树 map 对value值无要求 map 有序&#xff0c;按照key值自动排序 map key值唯一 map 头文件&#xff1a;#include map 支持重载[]的运算符 map 为保持有序性&#xff0c;erase()开销大 multimap multimap 红黑树 multim…...

2023年全国最新会计专业技术资格精选真题及答案11

百分百题库提供会计专业技术资格考试试题、会计考试预测题、会计专业技术资格考试真题、会计证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 一、选择题 1.下列各项中&#xff0c;仅将生产过程中消耗的变动成本计入产品成本…...

Centos7搭建NFS

1.NFS简介Network File System(网络文件系统&#xff0c;通过网络让不同的机器系统之间可以彼此共享文件和目录&#xff0c;类似Samba服务。2.NFS挂载原理 在网络中服务器和客户端进行连接都是通过端口进行数据传输&#xff0c;而NFS服务端的端口是随机的&#xff0c;从而导致N…...

ThreadLoca基本使用以及与synchronized的区别

文章目录1. ThreadLocal介绍1.1 官方介绍1.2 基本使用1.2.1 常用方法1.2.2 使用案例1.3 ThreadLocal类与synchronized关键字1.3.1 synchronized同步方式1.3.2 ThreadLocal与synchronized的区别2. 运用场景_事务案例2.1 转账案例2.1.1 场景构建2.1.2 引入事务2.2 常规解决方案2.…...

【C++】纯虚函数、纯虚析构

纯虚函数语法&#xff1a;virtual 返回值类型 函数名(参数列表) 0纯虚函数的作用&#xff1a;不用定义&#xff01;在多态中&#xff0c;通常父类中虚函数的实现是无意义的&#xff08;因为主要用子类重写的&#xff0c;父类只是为了派生子类当做一个类族的顶层出现&#xff0…...

Python 进阶小技巧:7招展开嵌套列表

大家好&#xff0c;今天给大家讲解一个Python的进阶知识点&#xff1a;如何将一个嵌套的大列表展开形成一个列表。 小编提供了7种方法供大家学习参考&#xff1a; for循环 列表推导式 使用第三方库itertools 使用sum函数 python自加&#xff08;&#xff09; 使用extend函…...

【Spring6】| Bean的作用域

目录 一&#xff1a;Bean的作用域 1. singleton&#xff08;单例&#xff09; 2. prototype&#xff08;多例&#xff09; 3. 其它scope 4. 自定义scop&#xff08;了解&#xff09; 一&#xff1a;Bean的作用域 1. singleton&#xff08;单例&#xff09; &#xff08;1…...

Qt界面美化之自定义qss样式表

原生的QT界面不好看&#xff0c;有时候需要根据美工的设计图修改样式。如果使用QML的话搞界面是快&#xff0c;但是QML有点儿吃内存&#xff0c;有时简单的功能还是用传统c的widget方便些。好在有qss&#xff0c;传统界面也可以美化的。QSS称为Qt Style Sheets也就是Qt样式表&a…...

春招进行时:“211文科硕士吐槽工资5500” HR:行情和能力决定价值

学历重要&#xff0c;还是能力重要&#xff1f; 春招进行时&#xff0c;不少学生求职遇冷&#xff0c;会把原因归结为学历水平不够高、毕业院校不够档次、专业不够热门、非一线城市就业机会少等等。 直到上海一位211大学的文科男硕士&#xff0c;吐槽招聘会提供的岗位薪资待遇…...

【DaVinci Developer专题】-45-自动生成SWC中所有Runnable对应的C文件

点击返回「Autosar从入门到精通-实战篇」总目录 案例背景(共5页精讲): 在DaVinci Developer中,以Test_A_SWC的Runnable为例,见图0-1。我们现在尝试自动生成一个包含Test_A_SWC_Init和Test_A_SWC_Main函数原型(也是适用于 C/S Port Serve Runnable)的C文件。 图0-1 目…...

redis启动和关闭服务脚本

编译安装redis&#xff0c;自己写了个脚本。 简单实现启动、关闭和 查看redis服务。 基本流程如下&#xff1a; 脚本执行&#xff0c;必须附带1个参数&#xff0c;没有参数会提示附带参数。 脚本会获取redis-server进程数量。作为开启、关闭以及查看redis服务的数据依据。 …...

windows CMD快捷键:

&#x1f431;个人主页&#xff1a;莎萌玩家&#x1f64b;‍♂️作者简介&#xff1a;全栈领域新星创作者、专注于全栈各领域技术&#xff0c;共同学习共同进步&#xff0c;一起加油呀&#xff01;&#x1f4ab;系列专栏&#xff1a;网络爬虫、WEB全栈开发&#x1f4e2;资料领取…...

【C/C++语言】刷题|双指针|数组|单链表

主页&#xff1a;114514的代码大冒 qq:2188956112&#xff08;欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ &#xff09; Gitee&#xff1a;庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com 文章目录 目录 文章目录 前言 一、删除有序数组中的重复项 二、合并两个有序数组 三&#xff0c;移除…...

Leetcode.1487 保证文件名唯一

题目链接 Leetcode.1487 保证文件名唯一 Rating &#xff1a; 1697 题目描述 给你一个长度为 n的字符串数组 names。你将会在文件系统中创建 n个文件夹&#xff1a;在第 i 分钟&#xff0c;新建名为 names[i]的文件夹。 由于两个文件 不能 共享相同的文件名&#xff0c;因此如…...

python-星号(*)-双星号(**)-函数动态参数匹配-解包操作

文章目录1.乘法和幂运算符2.函数接收数量不固定的入参3.限制函数入参仅以关键字形式输入4. 可迭代对象解包操作5.扩展可迭代对象解包1.乘法和幂运算符 ● 单个 * 用于乘法运算 ● 两个 ** 表示幂运算 >>> 2*3 >>> 6 >>> 2**3 >>> 82.函数…...

面试官:为什么说ArrayList线程不安全?

本博客知识点收录于&#xff1a;⭐️《JavaSE系列教程》⭐️ 1&#xff09;线程安全与不安全集合 我们学习集合的时候发现集合存在由线程安全集合和线程不安全集合&#xff1b;线程安全效率低&#xff0c;安全性高&#xff1b;反之&#xff0c;线程不安全效率高&#xff0c;安…...

STP详解

STP STP全称为“生成树协议”&#xff08;Spanning Tree Protocol&#xff09;&#xff0c;是一种网络协议&#xff0c;用于在交换机网络中防止网络回路产生&#xff0c;保证网络的稳定和可靠性。它通过在网络中选择一条主路径&#xff08;树形结构&#xff09;&#xff0c;并…...

linux AWK常用命令 —— 筑梦之路

搜集整理awk常用命令&#xff0c;以便使用查询 # 打印文件第一列awk {print $1} rumenz.txt# 打印文件前两列awk {print $1,$2} rumenz.txt# 打印文件最后一列awk {print $NF} rumenz.txt# 打印文件总行数awk END{print NR} rumenz.txt# 打印文件第一行awk NR1{print} rumenz.…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001

qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类&#xff0c;直接把源文件拖进VS的项目里&#xff0c;然后VS卡住十秒&#xff0c;然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分&#xff0c;导致编译的时候找不到了。因…...

无头浏览器技术:Python爬虫如何精准模拟搜索点击

1. 无头浏览器技术概述 1.1 什么是无头浏览器&#xff1f; 无头浏览器是一种没有图形用户界面&#xff08;GUI&#xff09;的浏览器&#xff0c;它通过程序控制浏览器内核&#xff08;如Chromium、Firefox&#xff09;执行页面加载、JavaScript渲染、表单提交等操作。由于不渲…...