Topic describes
This is 373 on LeetCode. Find the sum and the smallest k-pair number with medium difficulty.
Tag: “priority queue”, “binary”, “multiple merge”
Given two ascending arrays of integers nums1 and nums2, and an integer k.
Define a pair of values (u,v)(u,v)(u,v) where the first element comes from nums1 and the second from nums2.
Please find and the minimum number of k pairs (U1,v1), (u2,v2)… (uk,vk)(u_1,v_1), (u_2,v_2) … (u_k,v_k)(u1,v1), (u2,v2) … Vitamin k (UK).
Example 1:
Input: nums1 =,7,11 [1], nums2 = minus [2], k = 3 output: [1, 2], [1, 4], [1, 6] explanation: Return sequence of the first 3 logarithmic: [1, 2], [1, 4], [1, 6], [7, 2], [7, 4], [11], [7], [11, 4], [11]Copy the codeExample 2:
Input: nums1 =,1,2 [1], nums2 = [1, 2, 3], k = 2 output: [1, 1], [1, 1] explanation: Return sequence in the first 2 logarithmic: [1, 1], [1, 1], [1, 2], [2, 1], [1, 2], [2], [1, 3], [1, 3], [2, 3]Copy the codeExample 3:
Input: nums1 = [1, 2], nums2 = [3], k = 3 output: [1, 3], [2, 3] : may all the number in the sequence of are returned: [1, 3], [2, 3]Copy the codeTip:
Fundamental analysis
786. The KTH smallest prime number fraction is almost the same, which is the same first, there is no difference in difficulty 🤣
The most common way to do this is to use “multiple merge”. If you are not familiar with “multiple merge”, you are advised to learn 🧀 : Introduction to Multiple merge, which explains how to convert from “naive priority queue” to “multiple merge”.
Multi-channel merge
Let the length of nums1NUMs1nums1 be NNN, nums2nums2nums2 be MMM, and the number of all point pairs is N ∗mn * mn∗m.
Where each nums1[I]nums1[I]nums1[I] participates in the point sequence composed by:
As nums1Nums1NUMs1 and nums2nums2nums2 are sorted in ascending order, so the sequence of points that nums1[I]nums1[I]nums1[I]nums1[I] participates in is also sorted in ascending order, which leads us to use “multi-way merge” to solve.
Specifically, we put the first element (point pair) of these NNN sequences into the priority queue (small root heap) as a binary group (I,j)(I,j)(I,j), where iii is the subscript of nums1[I]nums1[I]nums1[I] in the point pair. JJJ is the subscript of nums2[j]nums2[j]nums2[j] nums2[j]. The complexity of this operation is O(nlogn)O(n\log{n})O(nlogn). A small optimization can also be made here: we always make sure that nums1nums1nums1 is the shorter of the two arrays, and then keep track of whether swapping has occurred by identifying bits to ensure the correct order of the answers.
Each time the top of the heap is fetched from the priority queue (heap), the answer is added, and the next bit (if any) in the sequence of the point pair is added to the priority queue.
For 🌰, first remove the binary group (0, 0) (0, 0) (0, 0), point to namely (nums1 [0], nums2 [0]) (nums1 [0], nums2 [0]) (nums1 [0], nums2 [0]). After fetching, the next locus pair of the sequence (NUMs1 [0], NUMs2 [1])(NUMs1 [0],nums2[1])(nums1[0], nums2[1]) is put into the priority queue in the form of binary (0,1)(0, 1)(0,1).
Can be proved by “inverse proof”, each such “take the current, put into the next” operation, can ensure that the current is not added to the answer of all point pairs of minimum value in the priority queue (heap), that is, the former KKK out of the heap of elements must be all points of the former KKK small value.
Code (thanks@BenhaoOther languages provided by students) :
class Solution {
boolean flag = true;
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> ans = new ArrayList<>();
int n = nums1.length, m = nums2.length;
if(n > m && ! (flag =false)) return kSmallestPairs(nums2, nums1, k);
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->(nums1[a[0]]+nums2[a[1]])-(nums1[b[0]]+nums2[b[1]]));
for (int i = 0; i < Math.min(n, k); i++) q.add(new int[]{i, 0});
while(ans.size() < k && ! q.isEmpty()) {int[] poll = q.poll();
int a = poll[0], b = poll[1];
ans.add(new ArrayList<>(){{
add(flag ? nums1[a] : nums2[b]);
add(flag ? nums2[b] : nums1[a]);
}});
if (b + 1 < m) q.add(new int[]{a, b + 1});
}
returnans; }}Copy the codeclass Solution:
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
flag, ans = (n := len(nums1)) > (m := len(nums2)), []
if flag:
n, m, nums1, nums2 = m, n, nums2, nums1
pq = []
for i in range(min(n, k)):
heapq.heappush(pq, (nums1[i] + nums2[0], i, 0))
while len(ans) < k and pq:
_, a, b = heapq.heappop(pq)
ans.append([nums2[b], nums1[a]] if flag else [nums1[a], nums2[b]])
if b + 1 < m:
heapq.heappush(pq, (nums1[a] + nums2[b + 1], a, b + 1))
return ans
Copy the codefunc kSmallestPairs(nums1 []int, nums2 []int, k int)[] []int {
n, m, ans := len(nums1), len(nums2), [][]int{}
flag := n > m
if flag {
n, m, nums1, nums2 = m, n, nums2, nums1
}
if n > k {
n = k
}
pq := make(hp, n)
for i := 0; i < n; i++ {
pq[i] = []int{nums1[i] + nums2[0], i, 0}
}
heap.Init(&pq)
for pq.Len() > 0 && len(ans) < k {
poll := heap.Pop(&pq).([]int)
a, b := poll[1], poll[2]
if flag{
ans = append(ans, []int{nums2[b], nums1[a]})
}else{
ans = append(ans, []int{nums1[a], nums2[b]})
}
if b < m - 1 {
heap.Push(&pq, []int{nums1[a] + nums2[b + 1], a, b + 1}}})return ans
}
// Minimum heap template
type hp [][]int
func (h hp) Len(a) int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i][0] < h[j][0]}func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.([]int))}func (h *hp) Pop(a) interface{} { a := *h; v := a[len(a)- 1]; *h = a[:len(a)- 1]; return v }
Copy the code- Time complexity: Let MMM be the minimum of NNN, MMM and KKK, and the complexity is O(M+k)∗logM)O(M +k) * \log{M})O(M+k)∗logM)
- Space complexity: O(M)O(M)O(M)
binary
We can also use dichotomy multiple times.
Suppose we sort all the sum of pairs in ascending order, The values on both ends are L = NUMs1 [0]+ NUMs2 [0] L = NUMs1 [0]+ NUMs2 [0] L = NUMs1 [0]+ NUMs2 [0] and R = NUMs1 [N −1]+ NUMs2 [m−1] R = NUMs1 [n-1]+ R = nums1 nums2 [m – 1] [n – 1) + nums2 [m – 1).
Therefore, we can perform dichotomy in the range [L,r][L,r][L,r] to find the first value XXX satisfying “the sum of point pairs is less than or equal to XXX, and the number exceeds KKK”.
The reason for this dichotomy is that the point pair and the number line in which XXX is located have a dichotomy:
- The number of point pairs and point pairs less than XXX is less than KKK;
- The number of point pairs whose sum is greater than or equal to XXX is greater than or equal to KKK.
To determine whether the number of point pairs less than or equal to XXX is greater than or equal to KKK, this step can be directly used to do the cycle, because the two points start from the middle value, this step will not run two layers of the cycle.
When the second KKK small value for XXX, due to the existence of different point pairs and value equal, we need to add the answer to all points and values less than or equal to XXX, and then as appropriate the value is equal to XXX point to add the answer, know to meet the number of answers KKK.
Nums1 [I]nums1[I]nums1[I]nums1[I]nums1[I] nums2nums2nums2 = x−nums1[I]x−nums1[I]x−nums1[I]
Finally, at all times, we can prune using the size of the answer array in relation to KKK.
Code:
class Solution {
int[] nums1, nums2;
int n, m;
public List<List<Integer>> kSmallestPairs(int[] n1, int[] n2, int k) {
nums1 = n1; nums2 = n2;
n = nums1.length; m = nums2.length;
List<List<Integer>> ans = new ArrayList<>();
int l = nums1[0] + nums2[0], r = nums1[n - 1] + nums2[m - 1];
while (l < r) {
int mid = l + r >> 1;
if (check(mid, k)) r = mid;
else l = mid + 1;
}
int x = r;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (nums1[i] + nums2[j] < x) {
List<Integer> temp = new ArrayList<>();
temp.add(nums1[i]); temp.add(nums2[j]);
ans.add(temp);
} else break; }}for (int i = 0; i < n && ans.size() < k; i++) {
int a = nums1[i], b = x - a;
int c = -1, d = -1;
l = 0; r = m - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums2[mid] >= b) r = mid;
else l = mid + 1;
}
if(nums2[r] ! = b)continue;
c = r;
l = 0; r = m - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums2[mid] <= b) l = mid;
else r = mid - 1;
}
d = r;
for (int p = c; p <= d && ans.size() < k; p++) {
List<Integer> temp = newArrayList<>(); temp.add(a); temp.add(b); ans.add(temp); }}return ans;
}
boolean check(int x, int k) {
int ans = 0;
for (int i = 0; i < n && ans < k; i++) {
for (int j = 0; j < m && ans < k; j++) {
if (nums1[i] + nums2[j] <= x) ans++;
else break; }}returnans >= k; }}Copy the code- Time complexity: Assuming that the value range of the sum of point pairs is MMM, the complexity of the first binary is O((n∗m)∗log m) O((n * m) * \log{m})O((n∗m)∗logM); If the sum of statistical point pairs is less than the target value XXX, the complexity is O(n∗m)O(n * m)O(n∗m). The complexity of counting the sum of all point pairs equal to the target value is O(Max (n∗logm,k))O(\ Max (n * \log{m}, k))O(Max (n∗logm,k)) (pruning takes advantage of the size relation in the whole process, most cycles will not run full, and the actual calculation amount will be lower than that of theoretical analysis).
- Space complexity: O(k)O(k)O(k)
The last
This is No.373 of our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some of which have locks, we will first brush all the questions without locks.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.