373. Find K Pairs with Smallest Sums

Problem

Bài toán yêu cầu tìm k cặp (u, v) với u thuộc nums1 và v thuộc nums2 sao cho tổng u + v là nhỏ nhất, với nums1 và nums2 đều đã được sắp xếp tăng dần

Approach

Nếu liệt kê tất cả các cặp rồi sort thì sẽ tốn O(mnlogmn), không tối ưu khi m, n lớn

Vì hai mãng đã sắp xếp, ta có thể dùng min_heap (priority queue) để luôn lấy ra cặp có tổng nhỏ nhất tiếp theo

Bắt đầu bằng cách ghép các phần tử nhỏ nhất của nums1 với phần tử nhỏ nhất của nums2

Mỗi lần lấy ra một cặp nhỏ nhất, tiếp tục đẩy vào heap cá cặp có khả năng nhỏ tiếp theo (tức là tăng chỉ số của một trong hai mảng)

Triển khai

Dùng min-heap đẻ lưu các tuple dưới dạng [sum, i, j] với i, j là chỉ số trong nums1, nums2

Khởi tạo heap với các cặp (nums1, nums2), (nums1[1], nums2), ..., (nums1 min(k, nums1.lerngth) 1], nums2).

Mỗi lần pop ra khỏi heap, thêm cặp cùng nums1[i] nhưng nums2[j + 1] nếu còn trong phạm vi

Lặp lại đến khi đủ k cặp hoặc heap rỗng

Solution

typescripttypescript

1function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] {
2    const res: number[][] = []
3    if (nums1.length === 0 || nums2.length === 0 || k === 0) return res;
4    const min_heap = new MinPriorityQueue<{ sum: number, i: number, j: number }>((val) => val.sum)
5    for (let i = 0; i < Math.min(nums1.length, k); i++) min_heap.enqueue({ sum: nums1[i] + nums2[0], i, j: 0 })
6    while (res.length < k && !min_heap.isEmpty()) {
7        const { i, j } = min_heap.dequeue()
8        res.push([nums1[i], nums2[j]])
9        if (j + 1 < nums2.length) min_heap.enqueue({ sum: nums1[i] + nums2[j + 1], i, j: j + 1 })
10    }
11    return res
12};

💡

Tóm tắt

Mỗi phần tử trong heap là một object chứa tổng, chỉ số i (nums1), chỉ số j (nums2)

Luôn lấy ra cặp có tổng số nhỏ nhất, sau đó chỉ đẩy thêm cặp tiếp theo của cùng nums1[i] nhưng nums2[j + 1]

Dùng khi lấy đủ k cặp hoặc heap rỗng

Loading content...

1function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] { 2 const res: number[][] = [] 3 if (nums1.length === 0 || nums2.length === 0 || k === 0) return res; 4 const min_heap = new MinPriorityQueue<{ sum: number, i: number, j: number }>((val) => val.sum) 5 for (let i = 0; i < Math.min(nums1.length, k); i++) min_heap.enqueue({ sum: nums1[i] + nums2[0], i, j: 0 }) 6 while (res.length < k && !min_heap.isEmpty()) { 7 const { i, j } = min_heap.dequeue() 8 res.push([nums1[i], nums2[j]]) 9 if (j + 1 < nums2.length) min_heap.enqueue({ sum: nums1[i] + nums2[j + 1], i, j: j + 1 }) 10 } 11 return res 12};

373. Find K Pairs with Smallest Sums

Related Posts

Related Posts

373. Find K Pairs with Smallest Sums

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists