重庆忠县网站建设公司哪家专业,短链接生成网址,宁波网络公司招聘信息,公司网络营销推广软件文章目录题目描述思路 代码题目描述 几天没打题#xff0c;感觉脑子都是一团浆糊。。。。 升序#xff1a;肯定得用这条件来优化复杂度数对#xff1a;用 int[2] 来表示
思路 代码
看了题解区彤哥的思路#xff0c;代码其实就 8 行 堆初始化…
文章目录题目描述思路 代码题目描述 几天没打题感觉脑子都是一团浆糊。。。。 升序肯定得用这条件来优化复杂度数对用 int[2] 来表示
思路 代码
看了题解区彤哥的思路代码其实就 8 行 堆初始化按照[i, 0]的规律初始化堆弹出当前堆顶就是最小值弹出[index1, index2]后往后最有可能的数对是[index1, index2 1]放入队列中继续循环
class Solution {public ListListInteger kSmallestPairs(int[] nums1, int[] nums2, int k) {// 小顶堆每次弹出最小的当前结果PriorityQueueint[] heap new PriorityQueue((a, b) - nums1[a[0]] nums2[a[1]] - (nums1[b[0]] nums2[b[1]])); // 策略模式// 堆初始化把 nums1 的所有索引入队nums2 的索引初始时都是 0// 优化最多入队 k 个就可以了因为提示中 k 的范围较小这样可以提高效率for (int i 0; i Math.min(k, nums1.length); i) heap.offer(new int[] {i, 0});ListListInteger ans new ArrayList();// 最多弹出 k 次获取 k 对数字while (k-- 0 !heap.isEmpty()) {// 弹出一个int[] pos heap.poll();ans.add(Arrays.asList(nums1[pos[0]], nums2[pos[1]])); // 每次都弹出一个当前的最小值// 加入一个将 index2 加 1 之后继续入队if (pos[1] nums2.length) heap.offer(pos);}return ans;}
}无注释版
class Solution {public ListListInteger kSmallestPairs(int[] nums1, int[] nums2, int k) {PriorityQueueint[] heap new PriorityQueue((a, b) - nums1[a[0]] nums2[a[1]] - (nums1[b[0]] nums2[b[1]])); for (int i 0; i Math.min(k, nums1.length); i) heap.offer(new int[] {i, 0});ListListInteger ans new ArrayList();while (k-- 0 !heap.isEmpty()) {int[] pos heap.poll();ans.add(Arrays.asList(nums1[pos[0]], nums2[pos[1]])); if (pos[1] nums2.length) heap.offer(pos);}return ans;}
}
