题目

给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

分析

大根堆（大顶堆）：大根堆即指在逻辑上的二叉树结构中，根结点>子结点，总是最大的，并且在堆的每一个局部都是这样。

小根堆（小顶堆）：与大根堆相反，即所有局部的根都小于子节点。

在java中优先队列是使用堆实现的。
主要有两个类

1. PriorityQueue 线程不安全
2. PriorityBlockingQueue 线程安全

我这里使用PriorityQueue，这一题我们可以通过一个大顶堆来维护一个答案序列

Jdk优先队列允许我们自定义比较器，可以比较的对象是可以使用优先队列的比较条件

PriorityQueue默认实现的是小顶堆，这里我们实现一个大顶堆

                PriorityQueue> queue = new PriorityQueue>(new Comparator>() {public int compare(List m, List n) {if(m.get(0) + m.get(1) < n.get(0) + n.get(1)){return 1;}else{return -1;}}});

到这里，我们可以进行两次for循环

class Solution {public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {List>result = new ArrayList<>();//构造有些队列，自定义比较器PriorityQueue> queue = new PriorityQueue>(new Comparator>() {public int compare(List m, List n) {if(m.get(0) + m.get(1) < n.get(0) + n.get(1)){return 1;}else{return -1;}}});//两次for循环，向优先队列中添加值for(int i = 0; i < nums1.length; i++){for(int j = 0; j < nums2.length; j++){if(queue.size() < k){queue.offer(Arrays.asList(nums1[i],nums2[j]));}else{if(nums1[i] + nums2[j] < queue.peek().get(0) + queue.peek().get(1)){queue.poll();queue.offer(Arrays.asList(nums1[i],nums2[j]));}else{if(nums1[i] > queue.peek().get(0) && nums2[j] > queue.peek().get(1)){break;}}}}}for(Listlist : queue){result.add(list);}return result;}
}

可能有人要问了，两次for循环为什么我不直接暴力遍历

因为：我们维护了一个答案序列，知道最大或最小值，我们可以轻松淘汰一些无效不必要的遍历，例如：

当的数组1新的值和数组2新的值大于维护的答案队列中堆顶最大的值的时候，这次遍历就是不必要的，可以结束本次小循环。

if(nums1[i] > queue.peek().get(0) && nums2[j] > queue.peek().get(1)){break;}

最后：

那么最后我给出一些常用的方法的解释：

1. boolean add（object）//将指定的元素插入此优先级队列。2. boolean offer（object）//将指定的元素插入此优先级队列。3. boolean remove（object）//从此队列中删除指定元素的单个实例（如果存在）。4. Object poll（）//检索并删除此队列的头部，如果此队列为空，则返回null。5.Object element（）//检索但不删除此队列的头部，如果此队列为空，则返回null。6.Object peek（）//检索但不删除此队列的头部，如果此队列为空，则返回null。7. void clear（）//从此优先级队列中删除所有元素。8. Comparator comparator（）//返回用于对此队列中的元素进行排序的比较器，如果此队列根据其元素的自然顺序排序，则返回null。9. boolean contains（Object o） //如果此队列包含指定的元素，则返回true。10.Iterator iterator（） //返回此队列中元素的迭代器。11.int size（）//返回此队列中的元素数。12.Object [] toArray（）//返回包含此队列中所有元素的数组。