leetcode 373. Find K Pairs with Smallest Sums | 373. 查找和最小的K对数字（小根堆）

水深无声 2022-08-30 15:52 125阅读 0赞

## 题目 ##

[https://leetcode.com/problems/find-k-pairs-with-smallest-sums/][https_leetcode.com_problems_find-k-pairs-with-smallest-sums]  
![在这里插入图片描述][566b7a77041118b2ebf4881682d32e29.png]

## 题解 ##

本来以为是个双指针+贪心，但是后来发现如果用双指针的话，指针并不是只能++，还需要往回走，否则会丢失一些组合

看了 Related Topics 之后才发现，这是个考察 Heap 的题。  
![在这里插入图片描述][05d37bbfe2cabdc77a87c5dfb5eff792.png]  
相关问题：[leetcode 347. Top K Frequent Elements | 347. 前 K 个高频元素（大根堆）][leetcode 347. Top K Frequent Elements _ 347. _ K]

于是复制之前的模板，建了个小根堆，搞定。

class Solution { 
        public static class HeapNode { 
            int sum;
            int n1;
            int n2;
    
            public HeapNode(int n1, int n2) { 
                this.n1 = n1;
                this.n2 = n2;
                this.sum = n1 + n2;
            }
        }
    
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { 
            List<List<Integer>> result = new ArrayList<>();
            int heapSize = nums1.length * nums2.length;
            HeapNode[] heap = new HeapNode[heapSize];
            // 建小根堆
            int p = 0;
            for (int n1 : nums1) { 
                for (int n2 : nums2) { 
                    heap[p++] = new HeapNode(n1, n2);
                }
            }
            for (int i = heapSize - 1; i >= 0; i--) // 自下向上建堆 可证复杂度为O(n)
                heapify(heap, i, heapSize);
            // Top k
            for (int i = 0; i < k && i < heap.length; i++) { 
                ArrayList<Integer> pair = new ArrayList<>();
                pair.add(heap[0].n1);
                pair.add(heap[0].n2);
                result.add(pair);
                // 堆调整
                swap(heap, 0, --heapSize);
                heapify(heap, 0, heapSize);
            }
            return result;
        }
    
        public void heapify(HeapNode[] heap, int i, int size) { 
            int left = i * 2 + 1;
            while (left < size) { 
                int mini = left + 1 < size && heap[left + 1].sum < heap[left].sum ? left + 1 : left; // 左右孩子较小者的下标
                mini = heap[mini].sum < heap[i].sum ? mini : i; // 两个孩子与父节点较小者的下标
                if (mini == i) break; // 不需要交换的情况
                swap(heap, mini, i);
                i = mini; // 更新i使其下沉
                left = 2 * i + 1;
            }
        }
    
        private void swap(HeapNode[] heap, int i, int j) { 
            HeapNode tmp = heap[i];
            heap[i] = heap[j];
            heap[j] = tmp;
        }
    }

![在这里插入图片描述][05c7ac53478bc8550d369a739123d9be.png]

[https_leetcode.com_problems_find-k-pairs-with-smallest-sums]: https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
[566b7a77041118b2ebf4881682d32e29.png]: /images/20220829/b4885787366b42e9a08648a89cddf0b6.png
[05d37bbfe2cabdc77a87c5dfb5eff792.png]: /images/20220829/f8b1c4710e874cb9b3c8ffbff2312745.png
[leetcode 347. Top K Frequent Elements _ 347. _ K]: https://hanquan.blog.csdn.net/article/details/118862834
[05c7ac53478bc8550d369a739123d9be.png]: /images/20220829/ef144b8e2cd24e40a132f51e5594b4c5.png