【Leetcode刷题篇】leetcode373 查找和最小的K对数字
发布日期:2021-06-29 15:33:35
浏览次数:3
分类:技术文章
本文共 1416 字,大约阅读时间需要 4 分钟。
给定两个以升序排列的整形数组 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]
示例 3:
输入: nums1 = [1,2], nums2 = [3], k = 3 输出: [1,3],[2,3] 解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
题解思路:用优先级队列来存储数组,用大顶堆来解决该题
package com.lcz.leetcode;/** * 查找和最小的K对数字 * @author LvChaoZhang * */import java.util.*;public class Leetcode373 { class Solution{ public List
> kSmallestPairs(int[] nums1,int[] nums2,int k){ // 存放结果 ArrayList
> res = new ArrayList<>(); // 大顶堆优先队列来解决问题 PriorityQueue queue = new PriorityQueue<>(k,((a,b)->compare(a,b))); // 构建topK for(int i:nums1) { for(int j:nums2) { int[] arr = new int[] { i,j}; if(k>queue.size()) { queue.offer(arr); }else if(compare(arr,queue.peek())>0) { queue.poll(); queue.offer(arr); } } } while(!queue.isEmpty()) { int[] poll = queue.poll(); res.add(0,Arrays.asList(poll[0],poll[1])); } return res; } // 定义比较 private int compare(int[] arr1,int[] arr2) { return (arr2[0]+arr2[1])-(arr1[0]+arr1[1]); } }}
转载地址:https://codingchaozhang.blog.csdn.net/article/details/109594578 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月21日 01时53分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Python抓取哔哩哔哩up主信息:只要爬虫学的好,牢饭吃的早
2019-04-29
有个码龄5年的程序员跟我说:“他连wifi从来不用密码”
2019-04-29
领导让我整理上个季度的销售额,幸好我会Python数据分析,你猜我几点下班
2019-04-29
【Python爬虫实战】为何如此痴迷Python?还不是因为爱看小姐姐图
2019-04-29
零基础自学Python,你也可以实现经济独立!
2019-04-29
数字化转型的主干道上,华为云以“三大关键”成企业智能化推手
2019-04-29
数字化为何不走“捷”“径”?
2019-04-29
和总裁、专家交朋友,华为云助推政企智能化升级又做到前面去了
2019-04-29
BCOP章鱼船长,6月22日晚上8点上线薄饼
2019-04-29
为战疫助力,半导体功不可没
2019-04-29
了解这些操作,Python中99%的文件操作都将变得游刃有余!
2019-04-29
知道如何操作还不够!深入了解4大热门机器学习算法
2019-04-29
只有经历过,才能深刻理解的9个编程道理
2019-04-29
发现超能力:这些数据科学技能助你更高效专业
2019-04-29
AI当道,人工智能将如何改变金融业?
2019-04-29
消除性别成见,技术领域需要更多“乘风破浪的姐姐”
2019-04-29
7行代码击败整个金融业,这对20多岁的爱尔兰兄弟是如何做到的?
2019-04-29
2020十大编程博客:私藏的宝藏编程语言博客大放送!
2019-04-29
编程中的角色选择:哪类工作角色最适合你?
2019-04-29