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

TopK题-快速选择方法

在这里插入图片描述

代码

class Solution {public int findKthLargest(int[] nums, int k) {//k 就是对应的是下标 n - k 的位置 也就是说我们要的是下标n-k的元素return quickselect(nums, 0, nums.length - 1, nums.length - k);}public int quickselect(int[] nums, int left, int right, int k) {while (left <= right) {int pivotIndex = partition(nums, left, right);// 直接判断 pivotIndex 是否为我们需要的目标位置if (pivotIndex == k) {return nums[pivotIndex];} else if (pivotIndex < k) {// 在右边找left = pivotIndex + 1;} else {// 在左边找right = pivotIndex - 1;}}return -1; // 不可能触发}// 你指定不变的 partition 方法int partition(int[] nums, int left, int right) {int pivot = nums[left];int i = left + 1;int j = right;while (i <= j) {while (i <= right && nums[i] <= pivot) i++;while (j >= left + 1 && nums[j] > pivot) j--;if (i < j) {swap(nums, i, j);}}// 将 pivot 放到中间位置(即 j 处)swap(nums, left, j);return j;}void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

时间复杂度分析

好的,我们来分析一下你提供的快速选择(Quickselect)算法实现的时间复杂度:

  1. 最好情况时间复杂度:

    • 当每次 partition 操作选取的 pivot 都恰好能将数组划分为两个大小相近的部分,并且我们要找的第 k 大元素总是位于较小的那个子数组中,或者 partition 操作第一次就找到了目标 pivotIndex == k
    • 在这种理想情况下,每次 partition 操作后,问题的规模大约减半。
    • 第一次 partition 需要 O(n) 时间。
    • 第二次大约需要 O(n/2) 时间。
    • 第三次大约需要 O(n/4) 时间。
    • 总的时间复杂度是 T(n) = O(n) + O(n/2) + O(n/4) + … + O(1)。这是一个等比数列求和,收敛于 O(2n)。
    • 因此,最好情况时间复杂度为 O(n)
  2. 最坏情况时间复杂度 :

    • 当每次 partition 操作选取的 pivot 都是当前子数组中的最小值或最大值时,并且我们要找的第 k 大元素总是位于那个包含剩下 n-1 个元素的较大子数组中。
    • 例如,如果数组已经有序(或逆序)、并且每次都选择第一个元素作为 pivot
    • 第一次 partition 需要 O(n) 时间、问题规模变为 n-1。
    • 第二次 partition 需要 O(n-1) 时间、问题规模变为 n-2。
    • 总的时间复杂度是 T(n) = O(n) + O(n-1) + O(n-2) + … + O(1)。这是一个等差数列求和。
    • 因此,最坏情况时间复杂度为 O(n^2)
  3. 平均情况时间复杂度 :

    • 在平均情况下,我们可以期望 partition 操作能够将数组划分得比较均匀。虽然不一定是严格的一半,但 pivot 大概率不会总是落在极端位置。
    • 可以证明(通常使用期望分析),每次 partition 后,问题的规模平均会减少一个常数比例(例如期望减少到 3n/4 或 n/2 等)。
    • 类似于最好情况的分析,时间复杂度的递推关系大致可以认为是 T(n) <= O(n) + T(αn),其中 α 是一个小于 1 的常数。
    • 解这个递推关系,可以得到 T(n) = O(n)。
    • 因此,平均情况时间复杂度为 O(n)

总结:

  • 最好情况: O(n)
  • 最坏情况: O(n^2)
  • 平均情况: O(n)

虽然最坏情况是 O(n^2)、但实际应用中、通过随机选择 pivot 或使用更健壮的 pivot 选择策略(如三数取中法)、可以大大降低遇到最坏情况的概率、使得算法的平均性能非常接近 O(n)。
我的代码使用了固定的 pivotnums[left])、

这里是引用

这使得它在面对特定输入(如已排序数组)时容易触发 O(n^2) 的最坏情况。

相关文章:

TopK题-快速选择方法

代码 class Solution {public int findKthLargest(int[] nums, int k) {//k 就是对应的是下标 n - k 的位置 也就是说我们要的是下标n-k的元素return quickselect(nums, 0, nums.length - 1, nums.length - k);}public int quickselect(int[] nums, int left, int right, int …...

【SpringBoot篇】详解短信验证码登录功能实现

一&#xff1a;需求分析与设计 1.1 发送短信验证码 &#xff08;1&#xff09;产品原型 &#xff08;2&#xff09;业务逻辑 &#xff08;3&#xff09;接口设计 1.2 短信验证码登录 &#xff08;1&#xff09;业务逻辑 …...

深入理解 Bash 中的 $‘...‘ 字符串语法糖

在 Bash 脚本编程中&#xff0c;字符串处理是不可或缺的一部分。为了让开发者更高效地处理特殊字符和控制字符&#xff0c;Bash 引入了一种独特的字符串语法糖&#xff1a;$&#xff08;带单引号的 ANSI-C 风格字符串&#xff09;。这种语法来源于 C 语言的 ANSI-C 标准&#x…...

机器人强化学习入门学习笔记(二)

基于上一篇的《机器人强化学习入门学习笔记》,在基于 MuJoCo 的仿真强化学习训练中,除了 PPO(Proximal Policy Optimization)之外,还有多个主流强化学习算法可用于训练机器人直行或其他复杂动作。 🧠 一、常见强化学习算法对比(可用于 MuJoCo) 算法类型特点适合场景PP…...

Vue3携手Echarts,打造炫酷数据可视化大屏

一、引言 在数字化时代&#xff0c;数据如同企业的血液&#xff0c;蕴含着巨大的价值。而如何将这些抽象的数据转化为直观、易懂的信息&#xff0c;以便更好地支持决策和展示成果&#xff0c;成为了众多开发者和企业关注的焦点。数据可视化大屏应运而生&#xff0c;它以直观、醒…...

Java Web项目部署指南2025

Java Web项目部署指南 适用场景&#xff1a;本地 Windows 开发打包 → 远程 Ubuntu 服务器部署&#xff08;2025年最佳实践&#xff09; 适合人群&#xff1a;Java Web初学者、运维新手、需要一站式部署流程的开发者 &#x1f680; 部署流程横向流程图 #mermaid-svg-aznXsajzfU…...

STC单片机与淘晶驰串口屏通讯例程之04【密码登录与修改】

大家好,我是『芯知识学堂』的SingleYork,上一讲笔者给大家介绍了STC单片机与淘晶驰串口屏通讯例程之03【单片机程序解析】,今天笔者要跟大家分享的淘晶驰串口屏的密码登录与密码修改功能的实现。 很多项目中,为了保护某些参数不被随意修改,往往需要增加密码来保护,这也是…...

青听音乐 1.0.6| 全网音乐免费听,无损下载,4条音源,界面简洁无广告

一款强大的音乐播放器&#xff0c;内部集成了相当丰富的功能&#xff0c;可以一键搜索任何想要的歌曲或歌手专辑&#xff0c;同时还支持下载和收藏&#xff0c;拥有非常流畅的速度&#xff0c;使用起来没有任何限制&#xff01;软件自带有大厂的解析音源&#xff0c;运行非常稳…...

FISCO BCOS【初体验笔记】

飞梭区块链搭建初体验笔记 环境部署创建四个节点的飞梭区块链用的VMware17 centos 7.9 区块链是飞梭2.0用的webase-frontJava环境的正确安装Webase-front搭建 智能合约设计一点合约调试笔记 智能合约abi文件转为go文件后端项目配置相关工具linux常用命令&#xff08;防忘记&…...

56.[前端开发-前端工程化]Day03-webpack构建工具

邂逅Webpack和打包过程 1 认识webpack工具 前端开发的流程 内置模块path path常见的API 在webpack中的使用 认识webpack 脚手架依赖webpack Webpack到底是什么呢 Webpack官方的图片 Vue项目加载的文件有哪些呢&#xff1f; Webpack的使用前提 Webpack的安装 2 webpack基本打包…...

两次解析格式化字符串 + 使用SQLAlchemy的relationship执行任意命令 -- link-shortener b01lersCTF 2025

题目描述: A fast and reliable link shortener service, with a new feature to add private links! 我们走一遍逻辑 注册 app.route("/register", methods[GET, POST]) def register(): """ 用户注册路由&#xff0c;处理用户注册请求&#xff…...

双目测量中的将视差图重投影成三维坐标图

双目测距主要步骤如下&#xff1a; 左右两张图片 → 匹配 → 得到视差图 disp&#xff1b; 使用 cv2.reprojectImageTo3D(disp, Q) 将视差图 重投影 成三维坐标图 → 得到 points_3d 什么是 points_3d&#xff1f; points_3d cv2.reprojectImageTo3D(disp, Q)points_3d.shap…...

WebAssembly(Wasm):现代Web开发的超级加速器

在当今的Web开发领域&#xff0c;性能和效率是开发者们永恒的追求目标。随着Web应用的复杂度不断增加&#xff0c;传统的JavaScript在某些场景下已经难以满足高性能计算和复杂逻辑处理的需求。此时&#xff0c;WebAssembly&#xff08;Wasm&#xff09;作为一种新兴的Web技术&a…...

学习黑客Nmap 命令法诀

筑基期第二重 — Nmap 命令法诀 修炼目标 这一重我们要把上一阶段学到的“神识探查原理”化成 实战招式&#xff1a;掌握日常最常用的 Nmap 命令&#xff0c;并能随心组合。每条命令都配上“修仙比喻”&#xff0c;让你边笑边记。 1. 基础法诀速查表&#xff08;凡修版&#xf…...

基于思考过程评价的心理问题咨询对话记性评估

基于思考过程评价的心理问题咨询对话记性评估 摘要: 在心理问题咨询的对话场景中,传统记性评价多局限于对话结果的相似度计算,无法全面捕捉来访者及咨询师在对话过程中的思维动态。本文提出一种聚焦此对话场景的记性评价新方法,将思考过程纳入评估范畴。详细阐释其基于认知…...

SQL数据库操作大全:从基础到高级查询技巧

大家好&#xff0c;欢迎来到程序视点&#xff01;我是你们的老朋友.小二&#xff01; SQL数据库操作核心语法精要 数据库基础操作 创建/删除数据库&#xff1a;CREATE DATABASE / DROP DATABASE 备份SQL Server&#xff1a;使用sp_addumpdevice和BACKUP DATABASE命令 数据库…...

基于MATLAB图像中的圆形目标识别和标记

一、前言 在数字图像处理中&#xff0c;有些图像类别可以使用圆形度进行区分。圆度有时被称为圆形度&#xff0c;其定义为&#xff1a;圆度 4πA / P&#xff0c;其中A是面积&#xff0c;P是周长。这个公式的来源是&#xff0c;对于圆来说&#xff0c;这个值等于1&#xff0c;…...

android-ndk开发(4): linux开发机有线连接android设备

android-ndk开发(4): linux开发机有线连接android设备 2025/05/05 1. 概要 linux 系统&#xff0c; 例如最常见的 ubuntu&#xff0c; 在通过 USB 线把 android 设备连接到开发机上时&#xff0c; 仅仅是 ”物理上的连接”。 这时候 adb 是无法识别到 android 设备的。 需要…...

相机biaoding

需要先安装linux客户端&#xff08;海康机器人官网&#xff09;&#xff0c;sudo dpkg -i MVS-2.1.2_x86_64_20221208.deb cd /opt/MVS/bin/ 再./MVS.sh运行,客户端启动。 打开海康相机客户端 cd /opt/MVS/bin export LD_LIBRARY_PATH/opt/MVS/bin/:$LD_LIBRARY_PATH ./MVS …...

linux 中inotify与inode的关系是什么?

在 Linux 系统中&#xff0c;inotify 和 inode 是两个密切相关但功能不同的概念&#xff0c;它们共同构成了文件系统的核心机制。以下是它们的关系解析&#xff1a; 一、基本概念 1. inode&#xff08;索引节点&#xff09; 定义&#xff1a;inode 是 Linux 文件系统中存储文…...

Paramiko 核心类关系图解析

类图关键说明 SSHClient 核心类 用户主要交互入口&#xff0c;聚合 Transport 对象依赖策略类处理主机密钥验证&#xff08;AutoAddPolicy/RejectPolicy&#xff09; Transport 引擎 管理底层连接生命周期组合 AuthHandler 处理认证逻辑组合 KexBase 实现密钥交换可创建多个 C…...

LeetCode算法题 (反转链表)Day17!!!C/C++

https://leetcode.cn/problems/reverse-linked-list/description/ 一、题目分析 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。今天这道题目非常的言简意赅&#xff0c;就是给定一个链表将其反转后返回反转后的头节点。 二、示例分析 输…...

3.5/Q1,GBD数据库最新一区文章解读

文章题目&#xff1a;Global burden of low vision and blindness due to age-related macular degeneration from 1990 to 2021 and projections for 2050 DOI&#xff1a;10.1186/s12889-024-21047-x 中文标题&#xff1a;1990年至2021年因年龄相关性黄斑变性导致的低视力和失…...

【AI论文】像素修补师(PixelHacker):具有结构和语义一致性的图像修复(Image Inpainting)

摘要&#xff1a;图像修复是图像编辑和图像生成之间的一个基础研究领域。 最近最先进的方法&#xff08;SOTA&#xff09;探索了新的注意力机制、轻量级架构和上下文感知建模&#xff0c;展示了令人印象深刻的性能。 然而&#xff0c;他们经常在复杂的结构&#xff08;如纹理、…...

卡洛诗中式西餐,打破“高价即高端”认知

在餐饮消费从“功能满足”向“意义消费”跃迁的今天&#xff0c;Z世代对饮食的期待早已超越“吃饱”的生理需求。萨莉亚原团队成员出来升级孵化的新概念西餐卡洛诗作为中式西餐赛道的破局者&#xff0c;通过场景重构、产品升维与情感绑定&#xff0c;将西餐体验转化为情绪的载体…...

Sui 上线两周年,掀起增长「海啸」

两年前的 5 月 3 日&#xff0c;Sui 的主网正式发布&#xff0c;将在开发网和测试网上验证过的下一代技术承诺变为现实。这一新兴网络旨在优化现有区块链技术&#xff0c;结合高性能计算环境与安全性、可验证性及韧性。 随着 Sui 迎来两周年&#xff0c;这股浪潮已成长为「海啸…...

手写 Vue 源码 === reactive 方法

目录 1. 响应式系统概述 2. Proxy与Reflect的应用 3. 响应式对象的创建 4. WeakMap的使用 主要特点 WeakMap 与 Map 的区别 应用场景 5. 依赖收集与触发更新 6. 响应式标记 7. 性能优化 8. 与Vue2的对比 9. 实际应用示例 10. 总结 Vue3的响应式系统是其核心特性…...

第一章-Rust入门

Rust 简介 Rust 是一种强类型的静态编程语言&#xff0c;它可以编写更快、更可靠的软件&#xff0c;兼备高层次的易用性与低层次的控制力。 Rust 具有以下几个特点&#xff1a; 内存安全&#xff0c;且不牺牲性能“编译通过就能正常运行”令人愉悦的语法和强大的语言特性优秀…...

【AI入门】Cherry入门1:Cherry Studio的安装及配置

前言 尝试了Trae配置MCP&#xff0c;测试了n8n设置MCP工作流&#xff0c;但感觉好累啊&#xff0c;CherryStudio横空出世&#xff0c;开着中文界面&#xff0c;就倍感亲切&#xff0c;看着大家操作很丝滑的样子&#xff0c;咱也鸟枪换炮了&#xff0c;哇哈哈&#x1f604;&…...

雷电模拟器-超好用的Windows安卓模拟器

一、雷电模拟器介绍 雷电模拟器是一款功能强大的软件&#xff0c;它能够在电脑上模拟出安卓手机系统&#xff0c;让你可以在电脑上运行各类手机应用及游戏。其采用虚拟安卓手机操作界面&#xff0c;为玩家带来了独特的体验。 &#xff08;一&#xff09;强大的兼容性 雷电模拟…...

数据集-目标检测系列- 蜥蜴 检测数据集 lizard >> DataBall

数据集-目标检测系列- 蜥蜴 检测数据集 lizard >> DataBall DataBall 助力快速掌握数据集的信息和使用方式。 贵在坚持&#xff01; * 相关项目 1&#xff09;数据集可视化项目&#xff1a;gitcode: https://gitcode.com/DataBall/DataBall-detections-100s/overview…...

Kubernetes控制平面组件:Controller Manager 之 NamespaceController 全方位讲解

云原生学习路线导航页&#xff08;持续更新中&#xff09; kubernetes学习系列快捷链接 Kubernetes架构原则和对象设计&#xff08;一&#xff09;Kubernetes架构原则和对象设计&#xff08;二&#xff09;Kubernetes架构原则和对象设计&#xff08;三&#xff09;Kubernetes控…...

数据结构小扫尾——栈

数据结构小扫尾——栈 jarringslee 文章目录 数据结构小扫尾——栈栈本质上是一种特殊的线性表。&#xff08;一&#xff09;线性表的定义&#xff08;二&#xff09;线性表的运算 什么是栈。&#xff08;一&#xff09;栈的定义&#xff08;二&#xff09;栈的分类&#xff0…...

策略模式(Strategy Pattern)

&#x1f9e0; 策略模式&#xff08;Strategy Pattern&#xff09; 策略模式是一种行为型设计模式&#xff0c;它允许定义一系列的算法或行为&#xff0c;然后将每个算法封装到一个类中&#xff0c;使得它们可以互换。策略模式让算法独立于使用它的客户端进行变化&#xff0c;…...

Qwen2_5-Omni-3B:支持视频、音频、图像和文本的全能AI,可在本地运行

Qwen2.5-Omni-3B是阿里云推出的全能AI模型。它能同时处理视频、音频、图像和文本。只有3B参数,却能在本地运行强大的多模态功能。 近日,已经在Hugging Face上发布。它是小型多模态AI系统的重要突破。 特点 Qwen2.5-Omni-3B与普通语言模型不同。它是真正的多模态系统,可以同…...

GZIPOutputStream 类详解

GZIPOutputStream 类详解 GZIPOutputStream 是 Java 中用于压缩数据为 GZIP 格式的输出流类&#xff0c;属于 java.util.zip 包。它是 DeflaterOutputStream 的子类&#xff0c;专门生成符合 GZIP 格式&#xff08;.gz 文件&#xff09;的压缩数据。 1. 核心功能 将数据压缩为…...

sudo useradd -r -s /bin/false -U -m -d /usr/share/ollama ollama解释这行代码的含义

这行命令用于为 OLLAMA 服务创建专用的系统用户&#xff0c;具体参数解析如下&#xff1a; sudo 以管理员权限执行命令&#xff0c;确保有足够权限创建系统用户。 useradd Linux 用户创建命令&#xff0c;用于在系统中新增用户。 -r 创建系统账户&#xff08;非登录用户&…...

自注意力(Self-Attention)和位置编码

自注意力 给定序列 x 1 , … , x n \mathbf{x}_1, \ldots, \mathbf{x}_n x1​,…,xn​, ∀ x i ∈ R d \forall \mathbf{x}_i \in \mathbb{R}^d ∀xi​∈Rd 自注意力池化层将 x i \mathbf{x}_i xi​ 当做key, value, query来对序列抽取特征得到 y 1 , … , y n \mathbf{y}…...

Linux压缩和解压类

一、gzip/gunzip 压缩 1、基本语法 gzip 文件 &#xff08;功能描述&#xff1a;压缩文件&#xff0c;只能将文件压缩为*.gz文件&#xff09; gunzip 文件.gz &#xff08;功能描述&#xff1a;解压缩文件命令&#xff09; 2、经验技巧 &#xff08;1&#…...

Kubernetes控制平面组件:Controller Manager详解

云原生学习路线导航页&#xff08;持续更新中&#xff09; kubernetes学习系列快捷链接 Kubernetes架构原则和对象设计&#xff08;一&#xff09;Kubernetes架构原则和对象设计&#xff08;二&#xff09;Kubernetes架构原则和对象设计&#xff08;三&#xff09;Kubernetes控…...

使用 JavaScript 实现数据导出为 Excel 和 CSV 文件

在 Web 开发中&#xff0c;经常会遇到需要将数据导出为文件的需求&#xff0c;例如将数据导出为 Excel 或 CSV 文件。今天&#xff0c;我们就来探讨如何使用 JavaScript 实现这一功能。 一、实现思路 我们通过 HTML 创建一个按钮&#xff0c;点击按钮时&#xff0c;触发 Java…...

设一个测试情境,新用户注册后显示的名字不完整,测试思路是怎么样的?

问题分析:新用户注册后显示名称不完整 典型表现:用户注册时输入"张三丰",系统仅显示"张"或"张三"等不完整信息 一、测试排查思维导图 二、详细测试方案 1. 前端测试 输入验证: 测试不同长度名称(1字符/10字符/50字符) 测试含空格名称(如…...

NHANES指标推荐:ZJU index

文章题目&#xff1a;Association between ZJU index and gallstones in US adult: a cross-sectional study of NHANES 2017-2020 DOI&#xff1a;10.1186/s12876-024-03553-9 中文标题&#xff1a;ZJU指数与美国成年人胆结石的关联&#xff1a;2017-2020年NHANES横断面研究 发…...

数据存储——高级存储之PV和PVC

一、概述 PV &#xff08; Persistent Volume &#xff09;是持久化卷的意思&#xff0c;是对底层的共享存储的一种抽象。一般情况下 PV 由 kubernetes 管理员进行创建和配置&#xff0c;它与底层具体的共享存储技术有关&#xff0c;并通过插件完成与共享存储的对接。 PVC &a…...

Astro Canvas 数据中心→设备一览大屏操作指南

✅ Astro Canvas 数据中心→设备一览大屏操作指南 📌 目标 通过API连接器 → 转换器 → 数据源 → 数据集 → Astro大屏设计,展示从 IoTDA 获取的设备影子数据,并在 Astro 大屏中以设备一览形式可视化展示(如设备ID、温度、湿度、烟雾浓度等状态)。 🔁 一、整体流程概…...

Cisco NDO - Nexus Dashboard Orchestrator

目录 一、什么是 Cisco NDO? 二、ND vs. NDO? 三、NDO vs. NDFC 四、NDO 用例: 一、什么是 Cisco NDO? Nexus Dashboard Orchestrator(NDO)可通过单一界面,实现跨多个数据中心的一致性网络与策略编排、可扩展性与灾难恢复等。 当在本地、多种私有云或公有云中同时运…...

Android 控件CalendarView、TextClock用法

一 UI代码 <?xml version="1.0" encoding="utf-8"?> <androidx.coordinatorlayout.widget.CoordinatorLayoutxmlns:android="http://schemas.android.com/apk/res/android"xmlns:app="http://schemas.android.com/apk/res-auto…...

Socket 编程 TCP

Socket 编程 TCP TCP socket API 详解V1 - Echo ServerV2 - Echo Server 多进程版本V3 - Echo Server 多线程版本V4 - Echo Server 线程池版本多线程远程命令执行v5 引入线程池版本翻译 TCP socket API 详解 socket(): socket()打开一个网络通讯端口,如果成功的话,就像 open…...

信息系统项目管理师-软考高级(软考高项)​​​​​​​​​​​2025最新(七)

个人笔记整理---仅供参考 项目立项管理 7.1项目建议与立项申请 项目建议书内容必背&#xff01; 7.2项目可行性研究 项目可行性研究必考 7.3项目的评估与决策...

Qt中的UIC

Qt中的UIC(User Interface Compiler, 用户界面编译器)&#xff1a;读取由Qt Widgets Designer生成的XML格式(.ui)文件并创建相应的C头文件或Python源文件。如将mainwindow.ui文件生成ui_mainwindow.h。 uic.exe位置在6.8.0\msvc2019_64\bin &#xff0c;其支持的输入参数如下所…...