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

Leetcode373.查找和最小的 K 对数字

文章目录

  • 题目描述
  • 解题思路
  • 代码

题目链接

题目描述

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

提示:

1 <= nums1.length, nums2.length <= 105
-109 <= nums1[i], nums2[i] <= 109
nums1 和 nums2 均为 升序排列
1 <= k <= 104
k <= nums1.length * nums2.length

解题思路

参考

多路归并的方法来解决这个问题,因为我们是找前k个最小的数,那么我们可以这样来,
令 nums1 的长度为 n,nums2 的长度为 m,所有的点对数量为 n×m。

其中每个 nums1[i] 参与所组成的点序列为:

[(nums1[0],nums2[0]),(nums1[0],nums2[1]),…,(nums1[0],nums2[m−1])]
[(nums1[1],nums2[0]),(nums1[1],nums2[1]),…,(nums1[1],nums2[m−1])]
[(nums1[n−1],nums2[0]),(nums1[n−1],nums2[1]),…,(nums1[n−1],nums2[m−1])]
由于 nums1 和 nums2 均已按升序排序,因此每个 nums1[i] 参与构成的点序列也为升序排序,这引导我们使用「多路归并」来进行求解。

怎么做呢?
既然是多路排序,那就是把以前的二路排序扩展一下,现在我们使用n路排序,我们按照上面的分法,就可以把序列分成n行,然后,我们可以在这n行中每次选最小的一个就好啦,这样选k次,就是我们要的答案了。
具体怎么实现呢?
我们其实的时候买把这n个序列的第一个元素(以二元组(i,j))入队(优先队列,或者是小根堆),其中 i 为该点对中 nums1[i] 的下标,j 为该点对中 nums2[j]的下标,这里可以有一个小优化,我们始终确保nums1为两数组中长度较小的那个,然后通过标记来记录是否发生过交换,确保答案的点顺序的正确性。
每次从优先队列中取出堆顶元素(这个堆顶就是当前未被加入到答案的所有点对中的最小值)加入答案,并将该点对所在序列的下一位(如果有的话)加入到优先队列。

代码

class Solution {boolean flag = true;public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {int n = nums1.length, m = nums2.length;if(n > m && !(flag = false))return kSmallestPairs(nums2, nums1, k);List<List<Integer>> ans = new ArrayList<>();PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> (nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]]));// 如果n>k的话,那我们其实只需要建立nums1的前k个序对就够了for(int i=0; i<Math.min(n, k) ;i++){q.add(new int[]{i,0});}while(ans.size() < k && !q.isEmpty()){int[] poll = q.poll();int a = poll[0], b= poll[1];ans.add(new ArrayList<>(){{add(flag ? nums1[a] : nums2[b]);add(flag ? nums2[b] : nums1[a]);}});if(b+1 < m)q.add(new int[]{a, b+1});}return ans;}
}

相关文章:

Leetcode373.查找和最小的 K 对数字

文章目录 题目描述解题思路代码 题目链接 题目描述 给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。 定义一对值 (u,v)&#xff0c;其中第一个元素来自 nums1&#xff0c;第二个元素来自 nums2 。 请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (…...

windows 安装 使用 nginx

windows 安装 使用 nginx nginx官网下载地址&#xff1a;https://nginx.org/en/download.html 下载稳定版本即可 下载压缩包解压到即可 进入文件夹中&#xff0c;打开命令行窗口&#xff0c;执行启动命令 start nginx.exe验证&#xff08;默认是80端口&#xff09;&#x…...

【运维】Linux 端口管理实用指南,扫描端口占用

在 Linux 系统中&#xff0c;你可以使用以下几种方法来查看当前被占用的端口&#xff0c;并检查 7860 到 7870 之间的端口&#xff1a; 推荐命令&#xff1a; sudo lsof -i :7860-7870方法一&#xff1a;使用 netstat 命令 sudo netstat -tuln | grep :78[6-7][0-9]这个命令…...

Android笔记--应用安装

这一节了解一下普通应用安装app的方式&#xff0c;主要是唤起系统来安装&#xff0c;直接上代码: 申请权限 <uses-permission android:name"android.permission.READ_EXTERNAL_STORAGE"/><uses-permission android:name"android.permission.WRITE_EXT…...

今日分享站

同志们&#xff0c;字符函数和字符串函数已经全部学习完啦&#xff0c;笔记也已经上传完毕&#xff0c;大家可以去看啦。字符函数和字符串函数and模拟函数 加油&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;...

基于python flask的旅游数据大屏实现,有爬虫有数据库

背景 随着旅游行业的快速发展&#xff0c;数据在旅游决策和规划中的重要性日益凸显。基于 Python Flask 的旅游数据大屏实现研究旨在结合爬虫技术和数据库存储&#xff0c;为用户提供全面、实时的旅游信息展示平台。 爬虫技术作为数据采集的重要手段&#xff0c;能够从各种网…...

海尔智家牵手罗兰-加洛斯,看全球创牌再升级

晚春的巴黎西郊&#xff0c;古典建筑群与七叶树林荫交相掩映&#xff0c;坐落于此的罗兰加洛斯球场内座无虚席。 来自全球各地的数万观众&#xff0c;正与场外街道上的驻足者们一起&#xff0c;等待着全世界最美好的网球声响起…… 当地时间5月26日&#xff0c;全球四大职业网…...

【busybox记录】【shell指令】unlink

目录 内容来源&#xff1a; 【GUN】【unlink】指令介绍 【busybox】【unlink】指令介绍 【linux】【unlink】指令介绍 使用示例&#xff1a; 删除文件 - 默认 常用组合指令&#xff1a; 指令不常用/组合用法还需继续挖掘&#xff1a; 内容来源&#xff1a; GUN &#x…...

如何恢复被盗的加密货币?

本世纪&#xff0c;网络犯罪的首要目标是加密货币。 这要归功于加密货币的日益普及和价值&#xff0c;网络犯罪分子已经认识到经济收益的潜力&#xff0c;并将重点转向利用这种数字资产中的漏洞。 在今天的文章中&#xff0c;我们将讨论加密货币恢复和被盗加密货币恢复。 我们…...

英语学习笔记29——Come in, Amy!

Come in, Amy! 进来&#xff0c;艾米&#xff01; shut v. 关严 区别&#xff1a;shut the door 把门关紧 口语&#xff1a;Shut up! 闭嘴&#xff01;    态度强硬&#xff0c;不礼貌 例句&#xff1a;请不要把门关严。    Don’t shut the door, please. bedroom n. …...

grpc NewClient 报错 name resolver error: produced zero addresses

场景 grpc版本: google.golang.org/grpc v1.64.0 连接客户端: import("google.golang.org/grpc""net" ) // 拿着设备ID 去获取连接 var connMap map[string]net.Conn conn, err : grpc.NewClient("device_id",grpc.WithContextDialer(func(ctx…...

【Docker】2、配置SSL证书远程访问Docker

1、使用 openssl 生成 ca 1、创建文件夹 mkdir -p /root/dockercd /root/docker2、创建 RSA 私钥 会提示 2 次输入证书密码&#xff0c;至少 4 位&#xff0c;创建后会生成一个 ca-key.pem 文件 openssl genrsa -aes256 -out ca-key.pem 4096得到 ca-key.pem 文件 3、创建…...

HFish蜜罐管理端搭建:构建网络安全的主动防御系统

引言 在网络攻防对抗日益激烈的今天&#xff0c;蜜罐技术作为一种有效的主动防御手段&#xff0c;越来越受到网络安全专家的青睐。HFish蜜罐以其强大的功能和灵活的部署方式&#xff0c;成为网络安全防护体系中的重要组成部分。本文将详细介绍如何在CentOS 7.6系统上搭建HFish…...

探秘AI艺术:揭开Midjourney绘画的神秘面纱

在当今这个数字化迅速发展的时代&#xff0c;AI技术已经深入到我们生活的方方面面&#xff0c;而最令人着迷的莫过于它在艺术创作领域的应用。“Midjourney绘画”就是这样一个令人惊叹的例子&#xff0c;它通过高级AI技术&#xff0c;能够帮助用户生成独一无二的艺术作品。但是…...

29-ESP32-S3-WIFI_Driver-00 STA模式扫描全部 AP

ESP32-S3 WIFI_Driver 引言 ESP32-S3是一款集成了Wi-Fi和蓝牙功能的芯片。关于WIFI的部分&#xff0c;其实内容比我想象的要多得多。所以通常来说&#xff0c;如果你想要编写自己的Wi-Fi应用程序&#xff0c;最快捷的方法就是先找一个类似的示例应用&#xff0c;然后将它的相…...

2024了,还有人在问为甚死锁?

大家好&#xff0c;我是javapub。 接上篇提到了锁&#xff0c;《InnoDB有哪些锁类型》。这么多的锁&#xff0c;你有遇到过死锁吗&#xff1f; 死锁是在事务数据库中会发生的一种特殊现象&#xff0c;多个事务在执行过程中&#xff0c;相互等待对方持有的资源&#xff0c;导致…...

Java中Arrays.toString与new String()字节数组使用的差异

Java 编程语言提供了许多内置方法和类&#xff0c;这使得程序员能够更加方便的处理数据和对象。本文将讨论 Arrays.toString 方法和 new String() 方法在处理字节数组时的不同。 文章目录 Arrays.toString 方法new String() 方法总结 Arrays.toString 方法 Arrays.toString() …...

开源表单流程设计器有哪几个突出的优势特点?

当前&#xff0c;传统的表单制作已经无法满足现在企业的发展需求了。想要实现高效率发展&#xff0c;需要引进先进的低代码技术平台、开源表单流程设计器等优秀软件平台助力发展。它们具有可视化操作界面、灵活好操作、易维护、效率高等诸多优势特点&#xff0c;在推动企业实现…...

景源畅信:抖音小店如何开橱窗?

在当今数字化时代&#xff0c;社交媒体平台不仅仅是人们交流和分享生活的工具&#xff0c;更成为了商家们展示和销售产品的重要场所。抖音作为一款流行的短视频社交应用&#xff0c;其内置的电商功能——抖音小店&#xff0c;为众多商家和个人提供了便捷的在线销售途径。其中&a…...

Unix环境高级编程--8-进程控制---8.7函数waitid 8.8函数wait3 wait4

1、Single Unix Specification支持一个取得进程终止状态的函数--waitid&#xff0c;此函数类似于waitpid&#xff1a; pid_t wait(int *status); pid_t waitpid(pid_t pid, int *status, int options); int waitid(idtype_t idtype, id_t id, siginfo_t *infop, int options); …...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...