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

LeetCode215数组中第K个最大元素

题目描述

  给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

解析

  快速排序的思想:每次确定当前轴的位置,因此可以对快速排序算法进行修改,每次找轴的位置,如果小则对后半进行递归,大则对前半部分进行递归。

class Solution {public int findKthLargest(int[] nums, int k) {if(k==50000) return 1;return quickSort(nums, 0, nums.length - 1, nums.length - k);}public int quickSort(int[] nums, int left, int right, int k){if (left == right) {return nums[left];}int base = nums[left];int low = left + 1;int high = right;while(low <= high) {while(low <= high && nums[low] <= base) {low ++;}while(low <= high && nums[high] > base) {high --;}if(low < high) {swap(nums, low, high);}}if(high == k) {return nums[left];}swap(nums, left, high);if(high < k) {return quickSort(nums, high + 1, right, k);}else {return quickSort(nums, left, high - 1, k);}}private void swap(int[] nums, int a, int b) {int temp = nums[a];nums[a] = nums[b];nums[b] = temp;}
}

  实际上,如果数据量不是特别大,可以更改算法,更简单且快捷。

class Solution {public int findKthLargest(int[] nums, int k) {int max = Arrays.stream(nums).max().getAsInt();int min = Arrays.stream(nums).min().getAsInt();int range = max - min + 1;int[] buckets = new int[range];for (int num : nums) {buckets[num - min]++;}for (int i = range - 1; i >= 0; i--) {k -= buckets[i];if (k <= 0) {return i + min;}}return -1;}
}

  针对上述解法,可以针对题目的输入进行时间优化.

class Solution {public int findKthLargest(int[] nums, int k) {int[] buckets = new int[20001];for (int i = 0; i < nums.length; i++) {buckets[nums[i] + 10000]++;}for (int i = 20000; i >= 0; i--) {k = k - buckets[i];if (k <= 0) {return i - 10000;}}return 0;}
}

在这里插入图片描述

相关文章:

LeetCode215数组中第K个最大元素

题目描述 给定整数数组 nums 和整数 k&#xff0c;请返回数组中第 k 个最大的元素。请注意&#xff0c;你需要找的是数组排序后的第 k 个最大的元素&#xff0c;而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 解析 快速排序的思想&#xff…...

LeetCode //C - 143. Reorder List

143. Reorder List You are given the head of a singly linked-list. The list can be represented as: L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form: L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not modify the values i…...

速盾:cdn如何解析?

CDN是内容分发网络&#xff08;Content Delivery Network&#xff09;的缩写&#xff0c;它是一种通过在全球范围内分布节点服务器来提供高性能、高可用性的网络服务的技术。CDN的主要功能是通过将内容分发到离用户更近的服务器节点&#xff0c;从而加速用户对网站、应用程序、…...

K8s集群调度续章

目录 一、污点&#xff08;Taint&#xff09; 1、污点&#xff08;Taint&#xff09; 2、污点组成格式 3、当前taint effect支持如下三个选项&#xff1a; 4、查看node节点上的污点 5、设置污点 6、清除污点 7、示例一 查看pod状态&#xff0c;模拟驱逐node02上的pod …...

大工作量LUAD代谢重编程模型多组学(J Transl Med)

目录 1&#xff0c;单细胞早期、晚期和转移性 LUAD 的细胞动力学变化 2&#xff0c;细胞代谢重编程介导的LUAD驱动恶性转移的异质性 3&#xff0c;模型构建 S-MMR评分管线构建 4&#xff0c;S-MMR 模型的预后评估 5&#xff0c; 还开发了S-MMR 评分网络工具 6&#xff0c…...

C语言#include<>和#include““有什么区别?

一、问题 有两种头⽂件包含的形式&#xff0c;⼀种是⽤尖括号将头⽂件括起&#xff0c;⼀种是⽤双引号将⽂件括起。那么&#xff0c;这两种形式有什么区别呢&#xff1f; 二、解答 这两种包含头⽂件的形式都是合法的&#xff0c;也是经常在代码中看到的&#xff0c;两者的区别…...

正在直播:Microsoft Copilot Studio 新增支持Copilot代理、Copilot扩展等多项功能

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

数据通信基本概念汇总

1. 数据通信基础 网关: 提供协议转换&#xff0c;路由选择&#xff0c;数据交换的网络设备 报文: 网络中所传递的一个数据单元。 数据载荷: 最终要传递的信息 封装: 给数据载荷添加头部和尾部的过程(形成新的报文) 解封装: 给数据载荷去掉头部和尾部的过程(获取数据载荷) 终端设…...

AcWing 835. Trie字符串统计——算法基础课题解

AcWing 835. Trie 字符串统计 题目描述 维护一个字符串集合&#xff0c;支持两种操作&#xff1a; I x 向集合中插入一个字符串 &#x1d465;&#xff1b;Q x 询问一个字符串在集合中出现了多少次。 共有 &#x1d441; 个操作&#xff0c;所有输入的字符串总长度不超过 1…...

RT-DETR算法改进【NO.1】借鉴CVPR2024中的StarNet网络StarBlock改进算法

前 言 YOLO算法改进的路有点拥挤,尝试选择其他的baseline作为算法研究,可能会更加好发一些文章。后面将陆续介绍RT-DETR算法改进的方法思路。 很多朋友问改进如何选择是最佳的,下面我就根据个人多年的写作发文章以及指导发文章的经验来看,按照优先顺序进行排序讲解…...

5,串口编程---实现简单的用串口发送接收数据

单片机通过串口向PC机发送数据 PC机通过串口接收单片机发过来的数据 1.UART和USART的区别&#xff1a; USART支持同步通信方式,可以通过外部时钟信号进行同步传输,而UART仅支持异步通信方式 本开发板STM32F103ZET6有5个串口&#xff0c;用串口1作调试串口&#xff0c;因为串…...

LeetCode583:两个字符串的删除操作

题目描述 给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 代码 解法1 /*dp[i][j]&#xff1a;以i-1为结尾的wrod1中有以j-1为尾的word2的个数为了让word1和word2相同&#xff0c;最少操作…...

LLama学习记录

学习前&#xff1a; 五大问题&#xff1a; 为什么SwiGLU激活函数能够提升模型性能&#xff1f;RoPE位置编码是什么&#xff1f;怎么用的&#xff1f;还有哪些位置编码方式&#xff1f;GQA&#xff08;Grouped-Query Attention, GQA&#xff09;分组查询注意力机制是什么&…...

如何克隆非默认分支

直接git clone下来的我们知道是默认分支&#xff0c;那如何克隆其他分支呢&#xff1a; 比如这个&#xff0c;我们想克隆AdvNet。 我们可以在本地文件夹打开Git Bash 依次输入&#xff1a; git clone --branch AdvNet https://github.com/wgcban/SemiCD.git cd SemiCD git b…...

数据结构——图

一 图论基本概念 Directed Acyclic Graph &#xff08;DAG&#xff09; 二 图的存储 ①邻接矩阵(适用于稠密图) ②邻接表(适用于稀疏图) 三、图的遍历 ①深度优先搜索 //(基于邻接表实现&#xff0c;以有向图为例) //DFS:Depth First Search 深度优先搜索 //1、访问起始顶点 …...

蓝桥杯—SysTick中断精准定时实现闪烁灯

在嵌入式系统中&#xff0c;SysTick_Handler 是一个中断服务例程&#xff08;Interrupt Service Routine, ISR&#xff09;&#xff0c;用于处理 SysTick 定时器的中断。SysTick 定时器通常用于提供一个周期性的定时中断&#xff0c;可以用来实现延时或者周期性任务。 SysTick…...

ML307R OpenCPU UDP使用

一、UDP通信流程 二、示例 三、UDP通信代码 一、UDP通信流程 ML307R UDP 是使用LWIP的标准的通信,具体UDP流程可以自行百度 二、示例 实验目的:实现把接收的数据再发送到服务端 测试网址:UDP电脑端测试网址 因为是4G,所以必须用外网的 /* 测试前请先补充如下参数 */…...

pod详解

目录 pod pod基本介绍 k8s集群中pod两种使用方式 pause容器使得Pod中所有容器共享两种资源&#xff1a;网络和存储 kubernetes中的pause容器主要为每个容器提供以下功能 k8s设计这样的pod概念和特殊组成结构有什么用意 pod分类 pod容器的分类 基础容器&#xff08;infr…...

免费插件集-illustrator插件-Ai插件-文本对象分行

文章目录 1.介绍2.安装3.通过窗口>扩展>知了插件4.功能解释5.总结 1.介绍 本文介绍一款免费插件&#xff0c;加强illustrator使用人员工作效率&#xff0c;进行文本对象分行。首先从下载网址下载这款插件 https://download.csdn.net/download/m0_67316550/87890501&…...

web学习笔记(五十九)

目录 1.style样式 1.1作用域 scoped 1.2 less和 sass 1.3 less和 sass两者的区别 2. 计算属性computed 3. 响应式基础reactive() 4. 什么是MVVM? 1.style样式 1.1作用域 scoped scoped表示样式作用域&#xff0c;把内部的样式仅限于当前组件模板生效&#xff0c;其…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...