文章目錄

• 題目描述
• 思路 && 代碼

題目描述

幾天沒打題，感覺腦子都是一團漿糊。。。。

• 升序：肯定得用這條件來優化復雜度
• 數對：用 int[2] 來表示
  

思路 && 代碼

• 看了題解區彤哥的思路，代碼其實就 8 行= =
• 堆初始化：按照[i, 0]的規律初始化堆
• 彈出：當前堆頂就是最小值，彈出[index1, index2]后，往后最有可能的數對是[index1, index2 + 1]，放入隊列中繼續循環～

class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {// 小頂堆，每次彈出最小的當前結果PriorityQueue<int[]> 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});List<List<Integer>> 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 List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {PriorityQueue<int[]> 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});List<List<Integer>> 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;} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记 - 每日一题】373. 查找和最小的 K 对数字（Java、堆、优先队列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。