本文共 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]);		}	}}
       
      
     
    
   

转载地址：http://kzwdf.baihongyu.com/