算法-堆/多路归并-查找和最小的 K 对数字

算法-堆/多路归并-查找和最小的 K 对数字

1 题目概述

1.1 题目出处

https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/?envType=study-plan-v2&envId=top-interview-150

1.2 题目描述

在这里插入图片描述

2 优先级队列构建大顶堆

2.1 思路

将两个数字的和放入大顶堆中,堆的最大大小为k。

当堆大小小于k时,直接放里面放。
当堆大小达到k后,比较当前元素和堆顶的元素,如果比堆顶元素小,就移除堆顶元素并放入当前元素。

最后,堆内元素就是和最小的K对数。

2.2 代码

class Solution {List<List<Integer>> resultList = new LinkedList<>();public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {// 大顶堆PriorityQueue<List<Integer>> queue = new PriorityQueue<>((o1, o2)->o2.get(0) + o2.get(1) - o1.get(0) - o1.get(1));for (int i = 0; i < Math.min(nums1.length, k); i++) {for (int j = 0; j < Math.min(nums2.length, k); j++) {int sum = nums1[i] + nums2[j];if (queue.size() < k) {List<Integer> pair = new ArrayList<>();pair.add(nums1[i]);pair.add(nums2[j]);queue.add(pair);} else {List<Integer> headPair = queue.peek();int headSum = headPair.get(0) + headPair.get(1);if (sum < headSum) {queue.poll();List<Integer> pair = new ArrayList<>();pair.add(nums1[i]);pair.add(nums2[j]);queue.add(pair);}}}}while (queue.size() > 0) {resultList.add(queue.poll());}return resultList;}
}

2.3 时间复杂度

O(Math.min(nums1.length, k) * Math.min(nums2.length, k))
在这里插入图片描述
悲催啊,超时了

2.4 空间复杂度

O(K)

3

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Spring面试题23:Spring支持哪些事务管理类型?Spring框架的事务管理有哪些优点?你更倾向用哪种事务管理类型?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:Spring支持哪些事务管理类型? Spring 支持以下几种事务管理类型: 编程式事务管理:通过在代码中显式地使用事务管理 API(如 TransactionTempla…

英飞凌 Tricore 架构中断系统详解

本文以TC3系列MCU为例&#xff0c;先来了解中断源是如何产生的&#xff0c;再看一下CPU是如何处理中断源的。 AURIX TC3XX的中断路由模块 Interrupt Router (IR) 在TC3中&#xff0c;中断既可以被CPU处理&#xff0c;也可以被DMA处理&#xff0c;所以手册中不再把中断称为中断…

Spring 学习(九)整合 Mybatis

1. 整合 Mybatis 步骤 导入相关 jar 包 <dependencies><dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.12</version><scope>test</scope></dependency><dependency>…

软件测试/测试开发丨岗位内推-58同城岗位开放~

58同城-测试工程师 岗位职责 1.参与需求分析、设计评审&#xff0c;制定测试计划&#xff0c;设计测试用例&#xff0c;搭建测试环境&#xff1b; 2.执行各级别和类型的测试&#xff0c;参与互联网测试的全流程&#xff1b; 3.借助最前沿的研发技术和理念&#xff0c;通过测…

短视频矩阵源码saas版开发---技术成品打磨

短视频矩阵源码saas版开发---技术成品打磨 企业要不要做抖音&#xff1f; 我的答案是要&#xff0c;而且要快&#xff0c;原因有以下几点&#xff1a; 1. 抖音高速增长未停&#xff0c;流量红利还未完全释放完&#xff0c;仍然有增长空间&#xff1b; 2. 抖音变现能力越来越…

《家的温暖,国庆团圆》

目录 &#x1f4d6; 引言 &#x1f4dd; 假日放假表 &#x1f365; 中秋节 &#x1f4da; 中秋节的由来 中秋节的仪式 &#x1f4da; 赏月 &#x1f4da; 吃月饼 &#x1f4da; 猜灯谜 &#x1f4da; 品茶赏花 &#x1f4da; 舞狮龙 &#x1f4da; 中秋节的感触 &am…

C++项目笔记--基于TensorRT搭建一个YoloV5服务器

目录 1--项目描述 2--项目地址 3--编译运行 4--测试结果 5--补充说明 1--项目描述 ① 基于 C/S 模型来构建 TCP 服务器和 TCP 客户端。 ② 使用 Epoll 来监控服务器和客户端之间的连接。 ③ 服务器和客户端约定使用相同的数据传输协议&#xff0c;头部分别使用 4 个字节来…

OpenCV查找和绘制轮廓:findContours和drawContours

1 任务描述&#xff1a; 绘制图中粗线矩形的2个边界&#xff0c;并找到其边界的中心线 图1 原始图像 2.函数原型 findContours( InputOutputArray image, OutputArrayOfArrays contours, OutputArray hierarchy, int mode, …

【C++】string 之 find、rfind、replace、compare函数的学习

前言 上篇文章&#xff0c;我们学习了assign、at、append这三个函数 今天&#xff0c;我们来学习find、 函数 find函数 引入 我们都知道&#xff0c;find函数可以是string类中&#xff0c;用于查找字符或者字符串的函数 也可以是&#xff0c;<algorithm>头文件中&am…

什么是Selenium?使用Selenium进行自动化测试!

你知道什么是 Selenium 吗&#xff1f;你知道为什么要使用它吗&#xff1f;答案就在本文中&#xff0c;很高兴能够与你共飧。 自动化测试正席卷全球&#xff0c;Selenium 认证是业界最抢手的技能之一。 什么是 Selenium&#xff1f; Selenium 是一种开源工具&#xff0c;用于…

96 # cookie

cookie 和 session 和 sessionStorage 和 localStorage localStorage 和 sessionStorage 本地储存&#xff08;发送请求不会携带&#xff09;&#xff0c;不能跨域localStorage 浏览器关闭后不会清空&#xff0c;必须手动清空sessionStorage 浏览器关闭后就会销毁http 无状态的…

如何使用 API 接口获取商品数据,从申请 API 接口、使用 API 接口到实际应用,一一讲解

在当今的数字化时代&#xff0c;应用程序接口&#xff08;API&#xff09;已经成为数据获取的重要通道。API 接口使得不同的应用程序能够方便地进行数据交换&#xff0c;从而促进了信息的广泛传播和利用。在众多的数据源中&#xff0c;商品数据是一个非常重要的领域&#xff0c…

postman怎么进行参数化?

一、先准备好参数化数据 &#xff08;参数化数据可以使用Excel或者txt的文件。 注意如果使用的是txt的文件&#xff0c;一定要使用英文的逗号&#xff0c;不然的话会报错&#xff01;&#xff09; 注意&#xff1a;填写好的数据后&#xff0c;保存的时候需要另存为&#xff0c…

接口自动化测试:pytest基础讲解

为什么要做接⼝测试&#xff1f; 只靠前端测试很难确保很⾼的覆盖率。接⼝测试&#xff0c;可以模拟出各种类型的⼊参&#xff0c;包括⼀些在前端模拟不出来的⼊参&#xff0c;还能根据接⼝⽂档的定义&#xff0c;设计出相对完善的⼊参值&#xff0c;在接⼝层保证质量&#xff…

燃尽图是什么?如何用它提升敏捷项目流程?

**敏捷项目管理**的核心是透明度和持续改进。燃尽图是轻松实现这两点的秘密武器。这种动态的可视化工具能有效地说明团队在一段时间内的进展情况&#xff0c;突出显示剩余的工作&#xff0c;并揭示你的团队是否在实现目标的正轨上。 敏捷项目管理中的燃尽图 燃尽图是敏捷项目…

mac怎么把两张图片拼在一起

mac怎么把两张图片拼在一起&#xff1f;在如今的生活中&#xff0c;喜欢摄影的朋友们越来越多。拍照已经成为我们的一种习惯&#xff0c;因为当我们遇到美景或迷人的人物时&#xff0c;总是忍不住按下快门&#xff0c;将它们定格。随着时间的推移&#xff0c;我们渐渐发现自己的…

【SQL】统一训练平台数据库实践--20230927

储存过程vlookup_peopledata_csodtraining 默认导出用今天批次的数据进行join on&#xff0c;先删除过渡表的资料&#xff0c;再将查询结果放在过渡表中。 BEGINDECLARE startdate varchar(50);SET startdate date_format(NOW(),%Y%m%d);DELETE FROM season.csod_data2;INSE…

项目04-基于Docker的Prometheus+Grafana+AlertManager的飞书监控报警平台

文章目录 一.项目介绍1.流程图2.拓扑图3.详细介绍 二.前期准备1.项目环境2.IP划分 三. 项目步骤1.ansible部署软件环境1.1 安装ansible环境1.2 建立免密通道1.3 批量部署docker 2 部署nginx、MySQL以及cadvisor、exporter节点2.1 在nginx节点服务器上面配置nginx、node_exporte…

可以动态改变刻度背景色的车速仪表盘

最近做的项目的主页面需要用到一个仪表盘来动态显示车速&#xff0c;同时改变对应的背景色 仪表盘 开始是想着使用echarts&#xff0c;修修改改拿来用&#xff0c;但是人家客户有规定&#xff0c;必须搞个差不多的&#xff0c;那没办法&#xff0c;自 己动手搞个吧 截图如下&am…

如何快速重置模型原点

1、什么是模型原点&#xff1f; 模型原点是三维建模中的概念&#xff0c;它是指在一个虚拟三维空间中确定的参考点。模型原点通常位于模型的几何中心或基本组件的中心位置。如图所示&#xff1a; 可以看到模型的原点在模型的几何中心 2、模型原点的作用 知道了什么是模型原点&…