[Java知识库]使用堆解决问题

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
//给定两个以升序排列的整形数组nums1,nums2，以及一个整数k，定义一堆值（u,v）其中第一个元素来自nums1,第二个元素来自nums2，找到和最小的k对数字（u1,v1）(u2,v2)
class Pair implements Comparable<Pair>{
    public int n1;
    public int n2;
    public int sum;
    public Pair(int n1,int n2){
        this.n1=n1;
        this.n2=n2;
        this.sum=n1+n2;
    }

    @Override
    public int compareTo(Pair o) {
        return this.sum-o.sum;
    }
}
public class HeapExam {
    public List<List<Integer>> kSmallestPairs(int[] nums1,int[] nums2,int k){
        List<List<Integer>> result=new ArrayList<>();

        if(nums1.length==0||nums2.length==0||k<=0){
            return result;
        }

        //当前需要前k大小的元素建立一个小堆
        PriorityQueue<Pair> queue=new PriorityQueue<>();
        //所有可能的数对都获取到并加入队列中
        for(int i=0;i<nums1.length;i++){
            for(int j=0;j<nums2.length;j++){
                queue.offer(new Pair(nums1[i],nums2[j]));
            }
        }
        //循环结束后，此时所有数对都在队列中，循环取出k个较小元素即可
        for(int i=0;i<k&&!queue.isEmpty();i++){
            Pair cur=queue.poll();
            List<Integer> tmp=new ArrayList<>();
            tmp.add(cur.n1);
            tmp.add(cur.n2);
            result.add(tmp);
        }
        return result;
    }
}