資訊專欄INFORMATION COLUMN
摘要：利用特點進行排序。我們需要構(gòu)建一個數(shù)據(jù)結(jié)構(gòu)，一個表示在的位置，一個表示在的位置，他們的和，用來排序。我們首先向里，和所有的元素的和。每次我們一組數(shù)，然后增加的會自然的進行排序。
Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Return: [1,2],[1,4],[1,6] The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
利用pq特點進行排序。 我們需要構(gòu)建一個數(shù)據(jù)結(jié)構(gòu)，一個pos表示在nums1的位置，一個pos表示在nums2的位置，他們的和，用來排序。 我們首先向PQ里offer，nums1[0] 和 所有nums2的元素的和。 每次我們poll一組數(shù)，然后增加nums1的pos, pq會自然的進行排序。操作K次就行了。
public class Solution {
public List kSmallestPairs(int[] nums1, int[] nums2, int k) {
List res = new ArrayList();
if(nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0 || k < 0) return res;
PriorityQueue pq = new PriorityQueue(new Comparator(){
public int compare(int[] a, int[] b){
return a[2] - b[2];
}
});
int m = nums1.length, n = nums2.length;
for(int i = 0; i < n; i++){
// t[0] pos in nums1, t[1] pos in nums2, val nums[t[0]]+nums[t[1]]
pq.offer(new int[]{0, i, nums1[0] + nums2[i]});
}
for(int i = 0; i < Math.min(k, m*n); i++){
int[] t = pq.poll();
res.add(new int[]{nums1[t[0]], nums2[t[1]]});
if(t[0] == m-1) continue;
pq.offer(new int[]{ t[0] + 1, t[1], nums1[t[0] + 1] + nums2[t[1]] });
}
return res;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/70081.html
摘要：題目鏈接先把一組里面和另外一組最小元素的組合放進，然后每次出和最小的，同時放進去有可能成為第二小的組合，即當前元素的下一個和元素的組合。 373. Find K Pairs with Smallest Sums 題目鏈接：https://leetcode.com/problems... greedy: 先把一組x里面和另外一組y最小元素的組合放進heap，然后每次poll出和最小的，同...
摘要：題目要求兩個單調(diào)遞增的整數(shù)數(shù)組，現(xiàn)分別從數(shù)組和數(shù)組中取一個數(shù)字構(gòu)成數(shù)對，求找到個和最小的數(shù)對。思路這題采用最大堆作為輔助的數(shù)據(jù)結(jié)構(gòu)能夠完美的解決我們的問題。每從堆中取走一個數(shù)對，就插入，從而確保堆中的數(shù)對都可以從小到大遍歷到。 題目要求 You are given two integer arrays nums1 and nums2 sorted in ascending order ...
摘要：復雜度是，其中。這做法和異曲同工?？戳司W(wǎng)上給的解法，沒有二分，二分的是結(jié)果。每次找到一個，然后求比它小的元素的個數(shù)，根據(jù)個數(shù)大于還是小于來二分。參考算的時候可以優(yōu)化 378. Kth Smallest Element in a Sorted Matrix 題目鏈接：https://leetcode.com/problems... 求矩陣里面第k小的數(shù)，首先比較容易想到的是用heap來做...
閱讀 1991·2021-09-26 10:19
閱讀 3266·2021-09-24 10:25
閱讀 1654·2019-12-27 11:39
閱讀 1937·2019-08-30 15:43
閱讀 683·2019-08-29 16:08
閱讀 3515·2019-08-29 16:07
閱讀 915·2019-08-26 11:30
閱讀 1279·2019-08-26 10:41
