資訊專欄INFORMATION COLUMN
摘要：題目鏈接先把一組里面和另外一組最小元素的組合放進(jìn)，然后每次出和最小的，同時(shí)放進(jìn)去有可能成為第二小的組合，即當(dāng)前元素的下一個(gè)和元素的組合。
373. Find K Pairs with Smallest Sums
題目鏈接：https://leetcode.com/problems...
greedy: 先把一組x里面和另外一組y最小元素的組合放進(jìn)heap，然后每次poll出和最小的，同時(shí)放進(jìn)去有可能成為第二小的組合，即當(dāng)前y元素的下一個(gè)和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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66628.html
摘要：題目要求兩個(gè)單調(diào)遞增的整數(shù)數(shù)組，現(xiàn)分別從數(shù)組和數(shù)組中取一個(gè)數(shù)字構(gòu)成數(shù)對，求找到個(gè)和最小的數(shù)對。思路這題采用最大堆作為輔助的數(shù)據(jù)結(jié)構(gòu)能夠完美的解決我們的問題。每從堆中取走一個(gè)數(shù)對，就插入，從而確保堆中的數(shù)對都可以從小到大遍歷到。 題目要求 You are given two integer arrays nums1 and nums2 sorted in ascending order ...
摘要：利用特點(diǎn)進(jìn)行排序。我們需要構(gòu)建一個(gè)數(shù)據(jù)結(jié)構(gòu)，一個(gè)表示在的位置，一個(gè)表示在的位置，他們的和，用來排序。我們首先向里，和所有的元素的和。每次我們一組數(shù)，然后增加的會自然的進(jìn)行排序。 Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Return: [1,2],[1,4],[1,6] The first 3 pairs are returne...
摘要：復(fù)雜度是，其中。這做法和異曲同工?？戳司W(wǎng)上給的解法，沒有二分，二分的是結(jié)果。每次找到一個(gè)，然后求比它小的元素的個(gè)數(shù)，根據(jù)個(gè)數(shù)大于還是小于來二分。參考算的時(shí)候可以優(yōu)化 378. Kth Smallest Element in a Sorted Matrix 題目鏈接：https://leetcode.com/problems... 求矩陣?yán)锩娴趉小的數(shù)，首先比較容易想到的是用heap來做...
閱讀 2958·2021-11-24 09:39
閱讀 2869·2021-09-29 09:34
閱讀 3561·2021-09-24 10:23
閱讀 1746·2021-09-22 15:41
閱讀 1701·2019-08-30 15:55
閱讀 3516·2019-08-30 13:58
閱讀 2624·2019-08-30 13:11
閱讀 1669·2019-08-29 12:31
