資訊專欄INFORMATION COLUMN
摘要：題目鏈接先把一組里面和另外一組最小元素的組合放進，然后每次出和最小的，同時放進去有可能成為第二小的組合，即當前元素的下一個和元素的組合。
373. Find K Pairs with Smallest Sums
題目鏈接：https://leetcode.com/problems...
greedy: 先把一組x里面和另外一組y最小元素的組合放進heap，然后每次poll出和最小的，同時放進去有可能成為第二小的組合，即當前y元素的下一個和x元素的組合。
public class Solution {
public List kSmallestPairs(int[] nums1, int[] nums2, int k) {
if(nums1.length == 0 || nums2.length == 0) return new ArrayList();
// heap: [nums1[i], nums2[j], i, j]
PriorityQueue minHeap = new PriorityQueue<>(k, (a, b) -> a[0] + a[1] - (b[0] + b[1]));
// add combination of element from one array with the first element of another
for(int i = 0; i < Math.min(nums1.length, k); i++) {
minHeap.offer(new int[] {nums1[i], nums2[0], i, 0});
}
// greedy
List result = new ArrayList();
while(k-- > 0 && !minHeap.isEmpty()) {
int[] cur = minHeap.poll();
int i = cur[2], j = cur[3];
result.add(new int[] {cur[0], cur[1]});
if(j + 1 < nums2.length) minHeap.offer(new int[] {nums1[i], nums2[j + 1], i, j + 1});
}
return result;
}
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66628.html
摘要：題目要求兩個單調遞增的整數數組，現分別從數組和數組中取一個數字構成數對，求找到個和最小的數對。思路這題采用最大堆作為輔助的數據結構能夠完美的解決我們的問題。每從堆中取走一個數對，就插入，從而確保堆中的數對都可以從小到大遍歷到。 題目要求 You are given two integer arrays nums1 and nums2 sorted in ascending order ...
摘要：利用特點進行排序。我們需要構建一個數據結構，一個表示在的位置，一個表示在的位置，他們的和，用來排序。我們首先向里，和所有的元素的和。每次我們一組數，然后增加的會自然的進行排序。 Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Return: [1,2],[1,4],[1,6] The first 3 pairs are returne...
摘要：復雜度是，其中。這做法和異曲同工?？戳司W上給的解法，沒有二分，二分的是結果。每次找到一個，然后求比它小的元素的個數，根據個數大于還是小于來二分。參考算的時候可以優化 378. Kth Smallest Element in a Sorted Matrix 題目鏈接：https://leetcode.com/problems... 求矩陣里面第k小的數，首先比較容易想到的是用heap來做...
閱讀 2950·2021-11-24 09:39
閱讀 2858·2021-09-29 09:34
閱讀 3549·2021-09-24 10:23
閱讀 1731·2021-09-22 15:41
閱讀 1690·2019-08-30 15:55
閱讀 3506·2019-08-30 13:58
閱讀 2614·2019-08-30 13:11
閱讀 1662·2019-08-29 12:31
