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

LeetCode 373 查找和最小的 K 对数字题解

LeetCode 373 查找和最小的 K 对数字题解

题目描述

给定两个以升序排列的整数数组 nums1 和 nums2,以及一个整数 k。定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2。请找到和最小的 k 个数对。

解题思路

最小堆优化法

  1. 初始候选集:将nums1每个元素与nums2第一个元素组合
  2. 堆维护:使用最小堆动态维护候选对
  3. 结果收集:每次取出堆顶元素后补充新的候选对

核心逻辑

  1. 堆元素结构:(sum, i, j) 存储当前和、nums1索引、nums2索引
  2. 避免重复:通过索引递增保证每个组合只处理一次
  3. 提前终止:当收集够k个结果或堆为空时停止

复杂度分析

操作时间复杂度空间复杂度
堆初始化O(klogk)O(k)
堆弹出/压入O(klogk)O(k)
总复杂度O(klogk)O(k)

测试用例

常规测试

输入:

nums1 = [1,7,11]
nums2 = [2,4,6] 
k = 3```python
# LeetCode 373 查找和最小的 K 对数字
# https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/import heapq
from typing import Listclass Solution:def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:"""解法:最小堆 + 双指针时间复杂度:O(klogk)空间复杂度:O(k)"""if not nums1 or not nums2:return []heap = []# 初始化堆:将nums1中每个元素与nums2第一个元素组合for i in range(min(len(nums1), k)):heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))result = []while heap and len(result) < k:# 取出当前最小和的组合val, i, j = heapq.heappop(heap)result.append([nums1[i], nums2[j]])# 将nums2的下一个元素加入堆(如果存在)if j + 1 < len(nums2):heapq.heappush(heap, (nums1[i] + nums2[j+1], i, j+1))return resultif __name__ == "__main__":# 测试用例test1 = Solution().kSmallestPairs([1,7,11], [2,4,6], 3)  # [[1,2],[1,4],[1,6]]test2 = Solution().kSmallestPairs([1,1,2], [1,2,3], 2)   # [[1,1],[1,1]]

相关文章:

LeetCode 373 查找和最小的 K 对数字题解

LeetCode 373 查找和最小的 K 对数字题解 题目描述 给定两个以升序排列的整数数组 nums1 和 nums2&#xff0c;以及一个整数 k。定义一对值 (u,v)&#xff0c;其中第一个元素来自 nums1&#xff0c;第二个元素来自 nums2。请找到和最小的 k 个数对。 解题思路 最小堆优化法…...

搜索二维矩阵 II 算法讲解

搜索二维矩阵 II 算法讲解 一、问题描述 给定一个 m x n 的二维矩阵 matrix ,需要在其中搜索一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。每列的元素从上到下升序排列。要求编写一个高效的算法来完成搜索任务。 二、解题思路 方法一:暴力枚举 …...

三层交换机,单臂路由(用DHCP自动配置ip+互通+ACL

三层交换机&#xff0c;单臂路由&#xff08;用DHCP自动配置ip互通ACL 任务 1.用DHCP自动配置ip 2.三层交换机SVI、 3.单臂路由 4.互通 5.ACL三层交换机SVI 交换机 Switch>en Switch#conf t Enter configuration commands, one per line. End with CNTL/Z. Switch(conf…...

OpenCV CUDA 模块中在 GPU 上对图像或矩阵进行 翻转(镜像)操作的一个函数 flip()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 cv::cuda::flip 是 OpenCV 的 CUDA 模块中的一个函数&#xff0c;用于在 GPU 上对图像或矩阵进行 翻转&#xff08;镜像&#xff09;操作。它类似…...

链表面试题7之相交链表

来了来了&#xff0c;这道题才是值得我们奇思妙想的题,链接在下面。 160. 相交链表 - 力扣&#xff08;LeetCode&#xff09; 看完题目一脸懵吗&#xff0c;没关系&#xff0c;我们还得看示例 还是一脸懵怎么办&#xff1f;&#xff1f; 两个链表相交的方式有几种&#xff1f;…...

Excel-to-JSON插件专业版功能详解:让Excel数据转换更灵活

前言 在数据处理和系统集成过程中&#xff0c;Excel和JSON格式的转换是一个常见需求。Excel-to-JSON插件提供了一套强大的专业版功能&#xff0c;能够满足各种复杂的数据转换场景。本文将详细介绍这些专业版功能的应用场景和使用方法。 订阅说明 在介绍具体功能之前&#xf…...

【C++】”如虎添翼“:模板初阶

泛型编程&#xff1a; C中一种使用模板来实现代码重用和类型安全的编程范式。它允许程序员编写与数据类型无关的代码&#xff0c;从而可以用相同的代码逻辑处理不同的数据类型。模板是泛型编程的基础 模板分为两类&#xff1a; 函数模板&#xff1a;代表了一个函数家族&#x…...

【K8S学习之探针】详细了解就绪探针 readinessProbe 和存活探针 livenessProbe 的配置

参考 Pod健康检查 Kubernetes 学习笔记Kubernetes 就绪探针&#xff08;Readiness Probe&#xff09; - 人艰不拆_zmc - 博客园Kubernetes存活探针&#xff08;Liveness Probe&#xff09; - 人艰不拆_zmc - 博客园 Pod健康检查 Pod的健康状态由两类探针来检查&#xff1a;…...

WSL 安装 Debian 12 后,Linux 如何安装 redis ?

在 WSL 的 Debian 12 上安装 Redis 的步骤如下&#xff1a; 1. 更新系统包列表 sudo apt update && sudo apt upgrade -y2. 安装 Redis sudo apt install redis-server -y3. 启动 Redis 服务 sudo systemctl start redis4. 设置开机自启 sudo systemctl enable red…...

python打卡day22

复习日 仔细回顾一下之前21天的内容&#xff0c;没跟上进度的同学补一下进度。 作业&#xff1a; 自行学习参考如何使用kaggle平台&#xff0c;写下使用注意点&#xff0c;并对下述比赛提交代码 kaggle泰坦里克号人员生还预测 就是很简单很草率地走了一遍机器学习的经典流程&am…...

国产化Excel处理控件Spire.XLS系列教程:如何通过 C# 删除 Excel 工作表中的筛选器

在 Excel 文件中&#xff0c;筛选器&#xff08;Filter&#xff09;是一个常用的数据处理工具&#xff0c;可以帮助用户快速按条件筛选数据行。但在数据整理完成、导出、共享或打印之前&#xff0c;往往需要 删除 Excel 工作表中的筛选器&#xff0c;移除列标题中的下拉筛选按钮…...

使用 DMM 测试 TDR

TDR&#xff08;时域反射计&#xff09;可能是实验室中上升时间最快的仪器&#xff0c;但您可以使用直流欧姆表测试其准确性。 TDR 测量什么 在所有高速通道中&#xff0c;反射都很糟糕。我们尝试设计一个通道来减少反射&#xff0c;这些反射都会导致符号间干扰 &#xff08;…...

基于卡尔曼滤波的传感器融合技术的多传感器融合技术(附战场环境模拟可视化代码及应用说明)

基于卡尔曼滤波的传感器融合技术的多传感器融合技术(附战场环境模拟可视化代码及应用说明) 1 目标运动状态空间建模1.1 状态向量定义1.2 状态转移方程1.3 观测模型构建2 卡尔曼滤波核心算法实现2.1 初始化2.2 预测步骤2.3 更新步骤3 多传感器融合仿真验证3.1 传感器模型模拟3…...

M8040A/M8199助力数据中心收发信机测试

随着数字通信和大数据的不断发展&#xff0c;误码率测试变得越来越重要。高性能误码率测试仪作为一种关键的测试设备&#xff0c;可以对数字信号进行高速、高精度的误码率测试&#xff0c;广泛应用于通信、数据中心、半导体等行业。 M8040A误码仪系统当前不仅在上游IP和顶层芯…...

傲云源墅:以五傲价值重构北京主城别墅格局

在高端别墅市场中&#xff0c;产品自身的品质与特色是吸引客户的关键。北京傲云源墅以其独特的 “五傲” 价值&#xff0c;重新定义了北京主城别墅的标准。 首先是低密之傲&#xff0c;傲云源墅的容积率低至约 0.9&#xff0c;与市场上 1.0 以上容积率的别墅相比&#xff0c;为…...

精益数据分析(56/126):创业阶段的划分与精益数据分析实践

精益数据分析&#xff08;56/126&#xff09;&#xff1a;创业阶段的划分与精益数据分析实践 在创业和数据分析的探索之旅中&#xff0c;理解创业阶段的划分以及与之对应的精益数据分析方法至关重要。今天&#xff0c;依旧怀揣着与大家共同进步的心态&#xff0c;深入研读《精…...

[redis进阶六]详解redis作为缓存分布式锁

目录 一 什么是缓存 缓存总结板书: 二 使⽤Redis作为缓存 三 缓存的更新策略 1) 定期⽣成 2) 实时⽣成 四 面试重点:缓存预热,缓存穿透,缓存雪崩 和缓存击穿 1)缓存预热 2)缓存穿透 3)缓存雪崩 4)缓存击穿 五 分布式锁 板书: 1)什么是分布式锁 2)分布式锁的基…...

【RabbitMQ】应用问题、仲裁队列(Raft算法)和HAProxy负载均衡

&#x1f525;个人主页&#xff1a; 中草药 &#x1f525;专栏&#xff1a;【中间件】企业级中间件剖析 一、幂等性保障 什么是幂等性&#xff1f; 幂等性是指对一个系统进行重复调用&#xff08;相同参数&#xff09;&#xff0c;无论同一操作执行多少次&#xff0c;这些请求…...

国产密码新时代!华测国密 SSL 证书解锁安全新高度

在数字安全被提升到国家战略高度的今天&#xff0c;国产密码算法成为筑牢网络安全防线的关键力量。华测国密SSL证书凭借其强大性能与贴心服务&#xff0c;为企业网络安全保驾护航&#xff0c;成为符合国家安全要求的不二之选&#xff01;​ 智能兼容&#xff0c;告别浏览器适配…...

【Linux篇章】Linux 进程信号2:解锁系统高效运作的 “隐藏指令”,开启性能飞跃新征程(精讲捕捉信号及OS运行机制)

本篇文章将以一个小白视角&#xff0c;通俗易懂带你了解信号在产生&#xff0c;保存之后如何进行捕捉&#xff1b;以及在信号这个话题中&#xff1b;OS扮演的角色及背后是如何进行操作的&#xff1b;如何理解用户态内核态&#xff1b;还有一些可以引出的其他知识点&#xff1b;…...

C# 基础 try-catch代码块

​ try-catch代码块是C#中用于异常处理的核心机制。异常是在程序执行过程中可能出现的错误&#xff0c;而try-catch代码块允许您在执行代码时捕获并处理这些异常。 一、基础结构 try {//可能抛出异常的代码 } catch (ArgumentException ex) {//处理特定异常 } catch (Excepti…...

为什么 mac os .bashrc 没有自动加载?

原因说明 在macOS中&#xff0c;默认情况下&#xff0c;终端使用的是Bash或Zsh作为shell。对于较新版本的macOS&#xff08;从Catalina开始&#xff09;&#xff0c;默认的shell已经切换为Zsh。因此&#xff0c;如果你正在使用Zsh&#xff0c;.bashrc文件不会自动生效&#xf…...

【HarmonyOS Next之旅】DevEco Studio使用指南(二十二)

目录 1 -> 开发静态共享包 1.1 -> 创建库模块 1.2 -> 编译库模块 2 -> 开发动态共享包 2.1 -> 使用约束 2.2 -> 开发动态共享包 2.2.1 -> 创建HSP模块 2.2.2 -> 编译HSP模块 3 -> 发布共享包 1 -> 开发静态共享包 HAR(Harmony Archive…...

QT6.8安装教程

官网下载 链接&#xff1a; Index of /official_releases/online_installers 这个比较慢 建议去 清华大学开源软件镜像站&#xff1a;Index of /qt/archive/online_installers/4.9/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 根据自己什么系统选择 点击打开…...

【Rust泛型】Rust泛型使用详解与应用场景

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

一周学完计算机网络之三:1、数据链路层概述

简单的概述 数据链路层是计算机网络体系结构中的第二层&#xff0c;它在物理层提供的基本服务基础上&#xff0c;负责将数据从一个节点可靠地传输到相邻节点。可以将其想象成一个负责在两个相邻的网络设备之间进行数据 “搬运” 和 “整理” 的 “快递中转站”。 几个重要概念…...

配置ssh无密登录

在root下有一个.ssh文件夹&#xff0c;它的下面有一个known_hosts文件&#xff0c;这个里面记录了哪些其他的主机通过ssh访问过当前的主机。 免密登录原理 &#xff08;2&#xff09;生成公钥和私钥 具体操作&#xff1a; 1. 进入 hadoop1001 2. 运行命令&#xff1a;ssh-keyg…...

南京邮电大学金工实习答案

一、金工实习的定义 金工实习是机械类专业学生一项重要的实践课程&#xff0c;它绝非仅仅只是理论知识在操作层面的简单验证&#xff0c;而是一个全方位培养学生综合实践能力与职业素养的系统工程。从本质上而言&#xff0c;金工实习是学生走出教室&#xff0c;亲身踏入机械加…...

无偿帮写毕业论文

以下教程教你如何利用相关网站和AI免费帮你写一个毕业论文。毕竟毕业论文只要过就行&#xff0c;脱产学习这么多年&#xff0c;终于熬出头了&#xff0c;完成毕设后有空就去多看看亲人好友&#xff0c;祝好&#xff01; 一、找一个论文模板(最好是overleaf) 废话不多说&#…...

【高数上册笔记01】:从集合映射到区间函数

【参考资料】 同济大学《高等数学》教材樊顺厚老师B站《高等数学精讲》系列课程 &#xff08;注&#xff1a;本笔记为个人数学复习资料&#xff0c;旨在通过系统化整理替代厚重教材&#xff0c;便于随时查阅与巩固知识要点&#xff09; 仅用于个人数学复习&#xff0c;因为课…...

大数据从专家到小白

文章目录 数据湖技术Apache Iceberg FlinkHiveHadoopHDFS 数据湖技术 Apache Iceberg Iceberg是一个通用的表格式&#xff08;数据组织格式&#xff09;&#xff0c;它可以适配Presto&#xff0c;Spark等引擎提供高性能的读写和元数据管理功能。 Flink Hive Hadoop HDFS...

特励达力科LeCroy推出Xena Freya Z800 800GE高性能的800G以太网测试平台

Xena Freya Z800 800GE 是由全球领先的测试与测量解决方案提供商特励达力科公司&#xff08;Teledyne LeCroy&#xff09;开发的高性能以太网测试平台&#xff0c;专为满足从10GE到800GE数据中心互连速度的需求而设计。特励达力科公司在网络测试领域拥有超过50年的技术积累&…...

LeetCode 热题 100 98. 验证二叉搜索树

LeetCode 热题 100 | 98. 验证二叉搜索树 大家好&#xff0c;今天我们来解决一道经典的二叉树问题——验证二叉搜索树。这道题在 LeetCode 上被标记为中等难度&#xff0c;要求判断给定的二叉树是否是一个有效的二叉搜索树&#xff08;BST&#xff09;。 问题描述 给你一个二…...

Linux文件编程——open函数

在 Linux 系统中&#xff0c;文件操作不仅仅通过高级语言的标准库进行&#xff0c;底层的文件操作是通过 系统调用 来实现的。系统调用 是用户空间与操作系统内核之间的接口&#xff0c;允许程序请求操作系统提供的服务&#xff0c;包括文件读写、内存管理、进程控制等。本文将…...

Linux-Ext系列文件系统

1.理解硬件 1.1磁盘 机械磁盘是计算机中唯⼀的⼀个机械设备 磁盘---外设 慢 容量⼤&#xff0c;价格便宜 1.2磁盘的物理结构 1.3磁盘的存储结构 扇区&#xff1a;是磁盘存储数据的基本单位&#xff0c;512字节&#xff0c;块设备 如何定位⼀个扇区呢&#xff1f; 可以先定…...

Multisim14使用教程详尽版--(2025最新版)

一、Multisim14前言 1.1、主流电路仿真软件 1. Multisim&#xff1a;NI开发的SPICE标准仿真工具&#xff0c;支持模拟/数字电路混合仿真&#xff0c;内置丰富的元件库和虚拟仪器&#xff08;示波器、频谱仪等&#xff09;&#xff0c;适合教学和竞赛设计。官网&#xff1a;艾…...

C——猜数字游戏

前面我们已经学习了C语言常见概念&#xff0c;数据类型和变量以及分置于循环的内容&#xff0c;现在我们可以将这些内容结合起来写一个有趣的小游戏。下面正式开始我们今天的主题——猜数字游戏的实现。 猜数字游戏的要求&#xff1a; 1.电脑自动生成1~100的随机数。 2.玩家…...

【iOS】SDWebImage源码学习

SDWebImage源码学习 文章目录 SDWebImage源码学习前言SDWebImage缓存流程sd_setImageWithURL(UIImageViewWebCache层)sd_internalSetImageWithURL(UIViewWebCache层)loadImageWithURL(SDWebManger层)queryCacheOperationForKey(SDImageCache层)删除缓存 callDownloadProcessFor…...

.Net HttpClient 处理响应数据

HttpClient 处理响应数据 1、初始化及全局设置 //初始化&#xff1a;必须先执行一次 #!import ./ini.ipynb2、处理响应状态 //判断响应码&#xff1a;正常 {var response await SharedClient.GetAsync("api/Normal/GetAccount?id1");if(response.StatusCode Sy…...

【心海资源】【最新话费盗u】【未测】提币对方官方波场+没有任何加密+无后门+前端VUE

提笔接口请使用官方提笔&#xff0c;第三方提笔都有风险 后门你们也扫扫&#xff0c;这种源码风险大&#xff0c;自己玩玩学习进行了 重要的事情说三遍 &#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&…...

Python中的标识、相等性与别名:深入理解对象引用机制

在Python编程中&#xff0c;理解变量如何引用对象以及对象之间的比较方式是至关重要的基础概念。本文将通过Lewis Carroll的笔名示例&#xff0c;深入探讨Python中的对象标识、相等性判断以及别名机制。 别名现象&#xff1a;变量共享同一对象 >>> charles {name: …...

Java 1.8(也称为Java 8)

Java 1.8&#xff08;也称为Java 8&#xff09;是Oracle于2014年发布的一个重要版本&#xff0c;引入了许多新特性和改进&#xff0c;极大地提升了Java语言的表达力和开发效率。以下是Java 1.8的主要新特性&#xff1a; ### 1. Lambda表达式 Lambda表达式是Java 1.8最具革命性…...

LVGL简易计算器实战

文章目录 &#x1f4c1; 文件结构建议&#x1f539; eval.h 表达式求值头文件&#x1f539; eval.c 表达式求值实现文件&#xff08;带详细注释&#xff09;&#x1f539; ui.h 界面头文件&#x1f539; ui.c 界面实现文件&#x1f539; main.c 主函数入口✅ 总结 项目效果&…...

Linux | Uboot-Logo 修改文档(第十七天)

01 Uboot 修改 首先我们在 home 目录下新建一个文件夹 imx6ull,然后打开 i.MX6ULL 终结者光盘资料\05_uboot linux源码,在 window 下解压下图箭头所指的压缩包,解压后分别得到 linux-imx-rel_imx_4.1.15_2.1.0_ga_20200323.tar.gz 和 uboot-imx-rel_imx_4.1.15_2.1.0_…...

数字孪生概念

数字孪生&#xff08;Digital Twin&#xff09; 是指通过数字技术对物理实体&#xff08;如设备、系统、流程或环境&#xff09;进行高保真建模和实时动态映射&#xff0c;实现虚实交互、仿真预测和优化决策的技术体系。它是工业4.0、智慧城市和数字化转型的核心技术之一。 1. …...

c++STL-string的使用

这里写自定义目录标题 string的使用string写成类模板的原因string的版本举例构造、析构函数和赋值重载构造函数和析构函数operator Iterators迭代器begin和endrbegin和rendcbegin和cend&#xff0c;crbegin和crend&#xff08;c11&#xff09; capacity容量有关函数不同编译器下…...

总结C/C++中程序内存区域划分

C/C程序内存分配的⼏个区域 1..栈区&#xff08;stack&#xff09;&#xff1a;在执⾏函数时&#xff0c;函数内局部变量的存储单元都可以在栈上创建&#xff0c;函数执⾏结束时 这些存储单元⾃动被释放。栈内存分配运算内置于处理器的指令集中&#xff0c;效率很⾼&#xff0c…...

C# 方法(方法重载)

本章内容: 方法的结构 方法体内部的代码执行 局部变量 局部常量 控制流 方法调用 返回值 返回语句和void方法 局部函数 参数 值参数 引用参数 引用类型作为值参数和引用参数 输出参数 参数数组 参数类型总结 方法重载 命名参数 可选参数 栈帧 递归 方法重载 一个类中可以有多个…...

Dockerfile 完全指南:从入门到最佳实践

Dockerfile 完全指南&#xff1a;从入门到最佳实践 1. Dockerfile 简介与作用 Dockerfile 是一个文本文件&#xff0c;包含了一系列用于构建 Docker 镜像的指令。它允许开发者通过简单的指令定义镜像的构建过程&#xff0c;实现自动化、可重复的镜像构建。 主要作用&#xf…...

DEEPPOLAR:通过深度学习发明非线性大核极坐标码(2)

目录 2.问题的提出和背景 2.1 信道编码 2.2.极化码 极坐标编码 极坐标解码 原文&#xff1a;《DEEPPOLAR: Inventing Nonlinear Large-Kernel Polar Codes via Deep Learning》 2.问题的提出和背景 2.1 信道编码 信道编码是一种为传输添加冗余的技术&#xff0c;使其对…...