Leetcode 215. 数组中的第K个最大元素

在这里插入图片描述

心路历程:

这道题本质上是排序不完全的过程,而且这道题有bug,直接用python的排序算法其实就能AC。
可以按照快排排到找到k-1个large元素的思维去做,不过这道题需要考虑空间复杂度,所以需要用指针快排。
其实也可以考虑用K次的冒泡排序。

注意的点:

1、思考递归函数需要只想当前层的处理逻辑,不要多深入往下一层去思考,否则容易乱
2、用快排来做这道题的递归函数不需要边界条件判断

98%AC:快排(内存超了)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick(alist):  # 将alist分为两部分查找
            nonlocal k
            target = alist[0]
            small, large = [], []  # 这块比较费内存
            for i in range(1, len(alist)):
                if alist[i] < target: small.append(alist[i])
                else: large.append(alist[i])
            
            if len(large) == k - 1: return target
            elif len(large) > k - 1: 
                return quick(large)
            else:
                k -= len(large) + 1 
                return quick(small)
       
        return quick(nums)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521197.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SUPS:一种用于自动驾驶的仿真地下泊车场景数据集

SUPS&#xff1a;一种用于自动驾驶的仿真地下泊车场景数据集 附赠自动驾驶学习资料和量产经验&#xff1a;链接 摘要 本文介绍了SUPS&#xff1a;一种用于自动驾驶的仿真地下泊车场景数据集。随着自动驾驶的范围扩大&#xff0c;自动地下泊车引起了人们极大的关注。自动驾驶汽…

【stm32】软件I2C读写MPU6050

软件I2C读写MPU6050(文章最后附上源码) 编码 概况 首先建立通信层的.c和.h模块 在通信层里写好I2C底层的GPIO初始化 以及6个时序基本单元 起始、终值、发送一个字节、接收一个字节、发送应答、接收应答 写好I2C通信层之后&#xff0c;再建立MPU6050的.c和.h模块 基于I2C通…

京东云幻兽帕鲁4核16G服务器优惠价格26元1个月、398元一年

京东云幻兽帕鲁4核16G服务器优惠价格26元1个月、658元1年、三年3098元&#xff0c;配置为&#xff1a;轻量云主机4C16G-100G SSD系统盘-5M带宽-1000G月流量 华北-北京&#xff0c;京东云优惠活动 yunfuwuqiba.com/go/jd 活动链接打开如下图&#xff1a; 幻兽帕鲁4核16G服务器优…

计算机网络-TCP重传、滑动窗口、流量控制、拥塞控制

重传机制 超时重传&#xff1a;超时重传时间&#xff08;RTO&#xff09;设定为略大于RTT&#xff08;动态&#xff09;。触发场景包括自己发送的数据包丢失和别人给自己的回应数据包丢失。启动重传机制后如果还没有收到数据包&#xff0c;则RTO设置为上次的两倍&#xff0c;直…

双连通分量算法

1. 连通图概念 连通图&#xff1a;无向图任意两点之间存在通路。 强连通&#xff1a;有向图&#xff08;前提&#xff09;中&#xff0c;任意两点都有至少一条通路&#xff0c;则此图为强连通图。 弱连通图&#xff1a;将有向图的有向边换成无向边得到的图是连通图&#xff0c…

Tomcat管理配置

Tomcat管理配置 1 host-manager项目2 manager项目 Tomcat 提供了Web版的管理控制台&#xff0c;位于webapps目录下。Tomcat 提供了用于管理Host的host-manager和用于管理Web应用的manager。 1 host-manager项目 Tomcat启动之后&#xff0c;可以通过 http://localhost:8080/ho…

Cortex-M7 外设(peripherals)总览

1 PPB内存映射总览 由Cortex-M7的内存映射模型可知&#xff0c;0xE000_0000~0xE00F_FFFF地址空间为私有外设总线 (Private peripheral bus&#xff0c;PPB)的内存区域&#xff0c;其具体的地址映射如表1所示。 表1 PPB寄存器内存映射 其中&#xff0c;注释后缀的相关含义如…

5.5.1MFC对话框——文件对话框

本文仅供学习交流&#xff0c;严禁用于商业用途&#xff0c;如本文涉及侵权请及时联系将于24小时内删除 目录 1.实验原理 2.示例说明 1.实验原理 CFileDialog类 用CFileDialog类提供的通用文件对话框&#xff0c;实现Windows标准的【打开】和【另存为】功能。 CFileD…

前端canvas项目实战——在线图文编辑器(八):复制、删除、锁定、层叠顺序

目录 前言一、效果展示二、实现步骤1. 复制2. 删除3. 锁定4. 层叠顺序 三、实现过程中发现的bug1. clone方法不复制自定义属性2. 复制「锁定」状态的对象&#xff0c;得到的新对象也是「锁定」状态 四、Show u the code后记 前言 上一篇博文中&#xff0c;我们细致的讲解了实现…

如何在没有备份的情况下从 iPad 恢复照片?

有很多操作都可能导致iPad照片丢失&#xff0c;包括误删除、出厂设置、iPad的iOS更新等。如果没有备份&#xff0c;似乎没有办法找回它们。然而&#xff0c;即使您将备份保留在 iCloud 或iTunes上&#xff0c;这些方式也需要您的 iPad 首先重置&#xff0c;从而用备份内容覆盖当…

Java-类型转换

Java数据类型转换的规则掌握后&#xff0c;将使我们对以后的学习事半功倍&#xff0c;下面是我列出的一些重点。 类型转换 由于Java是强类型语言&#xff0c;所以要进行有些运算的时候&#xff0c;需要用到类型转换。底到高依次是&#xff1a;byte,short,char->int->lo…

AJAX 原理

一、AJAX原理 - XMLHttpRequest 定义&#xff1a; 关系&#xff1a;axios 内部采用 XMLHttpRequest 与服务器交互。 好处&#xff1a;掌握使用 XHR 与服务器进行数据交互&#xff0c;了解 axios 内部原理。 1.1 使用 XMLHttpRequest&#xff1a; 步骤&#xff1a; 1. 创建 XM…

OpenHarmony开发-系统烧录

本文详细介绍了烧录OpenHarmony系统到开发板的操作流程。从基础的硬件准备和软件环境设置入手&#xff0c;详细说明了如何配置开发环境、构建系统镜像等过程&#xff0c;详细描述了烧录过程中的关键步骤&#xff0c;以及如何使用专用工具将OpenHarmony系统镜像传输到开发板。同…

ffmpeg 将多个视频片段合成一个视频

ffmpeg 将多个视频片段合成一个视频 References 网络视频 6 分钟的诅咒。 新建文本文件 filelist.txt filelist.txtfile output_train_video_0.mp4 file output_train_video_1.mp4 file output_train_video_2.mp4 file output_train_video_3.mp4 file output_train_video_4.m…

PowerJob 分布式任务调度简介

目录 适用场景 设计目标 PowerJob 功能全景 任务调度 工作流 分布式计算 动态容器 什么是动态容器? 使用场景 可维护性和灵活性的完美结合 实时日志&在线运维 PowerJob 系统组件 PowerJob 应用场景 PowerJob 的优势 PowerJob&#xff08;原OhMyScheduler&…

【opencv】示例-aruco_dict_utils.cpp 计算 ArUco 字典度量

该程序可用于计算 ArUco 字典度量。 要计算考虑翻转标记的指标&#xff0c;请使用 -r 标志。 该程序可用于创建和编写自定义 ArUco 词典。 #include <opencv2/objdetect/aruco_detector.hpp> // 包含aruco marker检测相关功能的头文件 #include <iostream> // 包含…

供应链领域主题:生产制造关键术语和系统

BOM&#xff08;Bill of Material&#xff09;物料清单 BOM&#xff08;Bill of Material&#xff09;物料清单&#xff0c;是计算机可以识别的产品结构数据文件&#xff0c;也是ERP的主导文件。BOM使系统识别产品结构&#xff0c;也是联系与沟通企业各项业务的纽带。ERP系统中…

(源码)基于Spring Boot和Vue植物养殖技巧学习系统的设计与实现

前言 &#x1f497;博主介绍&#xff1a;✌专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb; 精彩专栏 推荐订阅&#x1f447;&#x1f3fb; 2024年Java精品实战案例《100套》 &#x1f345;文末获取源码联系&#x1f345; &#x1f31f…

华为汽车的“计算+通信”电子电气架构

文章目录 整车结构 硬件平台 软件平台 总结展望 整车EEA&#xff08;电子电气架构&#xff09;&#xff0c;按照博世提出的演进路径&#xff0c;大致可以划分为四个阶段&#xff1a;分布式模块阶段、区域控制阶段、中央计算阶段、云计算阶段。示例如下&#xff1a; 本文选取…

MyBatis-Plus的学习笔记

MyBatis-Plus 一、MyBatis-Plus快速入门 1.1 简介 课程版本&#xff1a;3.5.3.1 https://baomidou.com/ MyBatis-Plus (opens new window)&#xff08;简称 MP&#xff09;是一个 MyBatis (opens new window) 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&…