【Leetcode刷题篇】leetcode373 查找和最小的K对数字
发布日期:2021-06-29 15:33:35
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月27日 22时40分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Hbase Shell 调用java代码:通过比较器,强过滤查询
2019-04-29
Linux防删除,恢复删除
2019-04-29
linux: shell脚本日常功夫
2019-04-29
linux脚本: 批量管理主机
2019-04-29
scala集合类型,函数
2019-04-29
spark: rdd的应用(scala api)
2019-04-29
spark: rdd的应用(java api)
2019-04-29
yarn: 资源调度机制
2019-04-29
spark的shell脚本分析
2019-04-29
推荐算法: 基于用户的协同过滤算法
2019-04-29
推荐算法:基于物品的协同过滤算法
2019-04-29
docker系列3:docker搭建CDH集群[单机单节点]
2019-04-29
ubuntu 16:使用系统自带的中文输入法
2019-04-29
k8s单机版[ microk8s ]
2019-04-29
docker系列6 :k8s集群[ 解压安装 ]
2019-04-29
maven- idea: 打包可执行jar
2019-04-29
docker系列2: windows安装docker
2019-04-29
hbase数据转移: 导入导出
2019-04-29
docker系列7: docker搭建mysql
2019-04-29
windows server 2012设置远程连接断开后自动注销
2019-04-29