当前位置: 首页 > 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.…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

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

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

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...