215数组中的第K个最大元素
215数组中的第K个最大元素
题目描述
给定整数数组 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] <= 104
方法一(小顶堆)
class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> pq = new PriorityQueue<>(); // min heapfor (int val : nums) {pq.add(val);if (pq.size() > k) {pq.poll();}}return pq.peek();}
}
在这个代码中,我们首先创建一个优先队列pq。然后,我们遍历数组nums,对于每个元素,我们将其添加到队列中。如果队列的大小大于k,我们就删除队列中的最小元素。最后,我们返回队列的头部元素,这就是第k个最大的元素。
这个算法的时间复杂度是O(n log k),因为我们需要对每个元素进行堆操作,堆操作的时间复杂度是O(log k)。虽然题目要求时间复杂度为O(n),但是这个算法在实际中的性能已经非常好了,因为log k通常远小于n。
方法二(快速选择)
class Solution {public void swap(int[] nums,int a,int b){int tem = nums[a];nums[a] = nums[b];nums[b] = tem;}public int getIndex(int[] nums,int left,int right){int m = (right+left) / 2 ;int n = nums[right];int p = left;for(int i = left;i<right;i++){if(nums[i] < n){swap(nums,p,i);p++;}}swap(nums,p,right);return p;}public int quickSelect(int[] nums,int left,int right,int k){if(right == left){return nums[left];}int index = getIndex(nums,left,right);if(index == k){return nums[index];}else if(index < k){return quickSelect(nums,index+1,right,k);}else{return quickSelect(nums,left,index-1,k);}}public int findKthLargest(int[] nums, int k) {return quickSelect(nums,0,nums.length-1,nums.length - k);}
}
快速选择是快速排序的一个优化,它在平均情况下的时间复杂度是O(n)。
在这个代码中,我们首先使用快速选择算法来找到第k个最大的元素。快速选择算法的基本思想是,我们选择一个枢轴元素,然后将数组分为两部分,一部分是小于枢轴的元素,另一部分是大于枢轴的元素。然后我们根据k和枢轴的位置,决定是在左边的部分还是右边的部分继续查找。如果k等于枢轴的位置,那么枢轴就是我们要找的元素。
相关文章:
215数组中的第K个最大元素
215数组中的第K个最大元素 题目描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。…...
【动态规划】【矩阵快速幂】LeetCode2851. 字符串转换
作者推荐 【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II 涉及知识点 【矩阵快速幂】封装类及测试用例及样例 LeetCode 2851. 字符串转换 给你两个长度都为 n 的字符串 s 和 t 。你可以对字符串 s 执行以下操作: 将 s 长度为 l (0 <…...
【LeetCode每日一题】单调栈 402 移掉k位数字
402. 移掉 K 位数字 给你一个以字符串表示的非负整数 num 和一个整数 k ,移除这个数中的 k **位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。 示例 1 : 输入:num "1432219", k 3 输出ÿ…...
力扣 309. 买卖股票的最佳时机含冷冻期
题目来源:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/ C题解:动态规划 状态1:表示持有股票。更新为之前持有股票(dp[i-1][0])或者不持有股票且不处于冷冻期后买入&…...
2024年刷题记录
马上要开始找实习了,又开始重启刷题计划了!加油冲冲冲!刷题的顺序follow代码随想录的60天刷题计划!感谢FuCosmo的总结!之前都是按照C的语法进行刷题的,这次也同样使用C。 Day 1 数组 这些题过年前都刷过了…...
【JGit 】简述及学习资料整理
JGit 介绍 [官网](JGit | The Eclipse Foundation): https://www.eclipse.org/jgit/ 用户指南 : https://github.com/eclipse-jgit/jgit/wiki/User-Guide JGit是一个用于Java编程语言的开源Git实现。它提供了一组Java库和API,使开发人员可以在他们的Java应用程序…...
python数据类型-集合set
1 集合(set)的定义 1.1 集合是一个无序且不重复元素的序列: 1)无序:存储顺序和添加的顺序不一定相同,不支持索引、切片 2)元素不重复:当添加重复元素时,集合会自动去重…...
excel如何指定求和
在Excel中,你可以使用函数来实现动态求和,使得当指定行的数值更新后,和也随之更新。具体来说,你可以使用SUM函数结合一些动态的引用方法。以下是一种实现方式: 假设你要对A列(从A1到A10,以示例…...
服务端实时推送技术之SSE(Server-Send Events)
文章目录 前言一、解决方案:1、传统实时处理方案:2、HTML5 标准引入的实时处理方案:3、第三方推送: 二、SSE1.引入库1、客户端: 2.服务端:三、业务实践:能否做到精准投递? 总结 前言…...
使用IntelliJ IDEA查看接口的全部实现方法
在大型Java项目中,经常会使用接口和抽象类进行代码设计。为了更好地了解代码结构和功能,我们需要快速查看一个接口的所有实现类。IntelliJ IDEA提供了一些方便的方法来实现这一目标。 1. 点击查看接口的实现子类 在IDEA中,你可以轻松地查看…...
阿里云幻兽帕鲁服务器操作系统类型怎么选择?
使用阿里云服务器搭建幻兽帕鲁操作系统类型选Windows还是Linux?如果对Linux熟悉就选择Linux,相对于windows,Linux更少占用系统资源;如果对Linux不熟悉,首选Windows。事实上,阿里云提供的幻兽帕鲁服务器通过…...
Codeforces Round 927 (Div. 3) LR-remainders的题解
原题描述: C.LR-remains 每次测试时限:2 秒 每次测试的内存限制:256 兆字节 输入:标准输入 输出:标准输出 样例1输入: 4 4 6 3 1 4 2 LRRL 5 1 1 1 1 1 1 LLLLL 6 8 1 2 3 4 5 6 RLLLRR 1 10000 1000…...
HarmonyOS—@Observed装饰器和@ObjectLink嵌套类对象属性变化
Observed装饰器和ObjectLink装饰器:嵌套类对象属性变化 概述 ObjectLink和Observed类装饰器用于在涉及嵌套对象或数组的场景中进行双向数据同步: 被Observed装饰的类,可以被观察到属性的变化;子组件中ObjectLink装饰器装饰的状…...
The method toList() is undefined for the type Stream
The method toList() is undefined for the type Stream (JDK16) default List<T> toList() { return (List<T>) Collections.unmodifiableList(new ArrayList<>(Arrays.asList(this.toArray()))); }...
vue+element (el-progress)标签 隐藏百分比(%) ,反向显示 ,自定义颜色, demo 复制粘贴拿去用
1 效果: 2 页面代码: <el-row :gutter"10" ><el-col :span"12"><el-card ><div class"fourqu"><div><span slot"title">{{推送任务TOP5}}</span></div></div><div class&…...
Android轻量级进程间通信Messenger源码分析
一. 概述 Android中比较有代表性的两大通信机制:1. 线程间Handler通信 2. 进程间Binder通信,本篇文章中我们在理解AIDL原理的基础上来解读一下Messenger的源代码, 并结合示例Demo加深理解。 在看本篇文章前,建议先查阅一下笔者的…...
C#开发AGV地图编辑软件
C#自己开发AGV地图编辑软件: 1、自由添加和删除站点、停车位、小车、运行路径。 2、编辑得地图以XML文件保存。 3、导入编辑好地图的XML文件。 4、程序都是源码,可以直接在此基础上进行二次开发。 下载链接:https://download.csdn.net/d…...
嵌入式学习day22 Linux
文件IO: 1. lseek off_t lseek(int fd, off_t offset, int whence); 功能: 重新设定文件描述符的偏移量 参数: fd:文件描述符 offset:偏移量 whence: SEEK_SET 文件开头 …...
不确定性问题的论文笔记
Statistics starting from 01/2024, 仅列出了优秀工作中的一部分 每一年的排列顺序: CVPR, ICLR, ECCV, ICCV, ICML, AAAI, TPAMI,TIP,Arxiv 等 每周更新 2024 论文信息速览笔记是 否 已精读精读笔记Shao W, Xu Y, Peng L, et al. Failure Detection fo…...
C语言推荐书籍
本书详细讲解了C语言的基本概念和编程技巧。全书共17章。第1章、第2章介绍了C语言编程的预备知识。第3章~第15章详细讲解了C语言的相关知识,包括数据类型、格式化输入/输出、运算符、表达式、语句、循环、字符输入和输出、函数、数组和指针、字符和字符串…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...
