373. Find K Pairs with Smallest Sums
leetcode medium
Task
Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k.
Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива.
Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами.
Пример:
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: 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]
C# solution
matched/originalusing System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> KSmallestPairs(int[] nums1, int[] nums2, int k) {
int m = nums1.Length, n = nums2.Length;
var ans = new List<IList<int>>();
var visited = new HashSet<(int, int)>();
var minHeap = new SortedSet<(int, int, int)>();
minHeap.Add((nums1[0] + nums2[0], 0, 0));
visited.Add((0, 0));
while (k-- > 0 && minHeap.Count > 0) {
var top = minHeap.Min;
minHeap.Remove(top);
int i = top.Item2, j = top.Item3;
ans.Add(new List<int> { nums1[i], nums2[j] });
if (i + 1 < m && !visited.Contains((i + 1, j))) {
minHeap.Add((nums1[i + 1] + nums2[j], i + 1, j));
visited.Add((i + 1, j));
}
if (j + 1 < n && !visited.Contains((i, j + 1))) {
minHeap.Add((nums1[i] + nums2[j + 1], i, j + 1));
visited.Add((i, j + 1));
}
}
return ans;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public IList<vector<int>> KSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int m = nums1.size(), n = nums2.size();
var ans = new List<vector<int>>();
var visited = new HashSet<(int, int)>();
var minHeap = new SortedSet<(int, int, int)>();
minHeap.push_back((nums1[0] + nums2[0], 0, 0));
visited.push_back((0, 0));
while (k-- > 0 && minHeap.size() > 0) {
var top = minHeap.Min;
minHeap.Remove(top);
int i = top.Item2, j = top.Item3;
ans.push_back(new List<int> { nums1[i], nums2[j] });
if (i + 1 < m && !visited.Contains((i + 1, j))) {
minHeap.push_back((nums1[i + 1] + nums2[j], i + 1, j));
visited.push_back((i + 1, j));
}
if (j + 1 < n && !visited.Contains((i, j + 1))) {
minHeap.push_back((nums1[i] + nums2[j + 1], i, j + 1));
visited.push_back((i, j + 1));
}
}
return ans;
}
}Java solution
matched/originalimport java.util.*;
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
int m = nums1.length, n = nums2.length;
List<List<Integer>> ans = new ArrayList<>();
Set<Pair<Integer, Integer>> visited = new HashSet<>();
PriorityQueue<Triple> minHeap = new PriorityQueue<>(Comparator.comparingInt(t -> t.sum));
minHeap.add(new Triple(nums1[0] + nums2[0], 0, 0));
visited.add(new Pair<>(0, 0));
while (k-- > 0 && !minHeap.isEmpty()) {
Triple top = minHeap.poll();
int i = top.i, j = top.j;
ans.add(Arrays.asList(nums1[i], nums2[j]));
if (i + 1 < m && !visited.contains(new Pair<>(i + 1, j))) {
minHeap.add(new Triple(nums1[i + 1] + nums2[j], i + 1, j));
visited.add(new Pair<>(i + 1, j));
}
if (j + 1 < n && !visited.contains(new Pair<>(i, j + 1))) {
minHeap.add(new Triple(nums1[i] + nums2[j + 1], i, j + 1));
visited.add(new Pair<>(i, j + 1));
}
}
return ans;
}
class Triple {
int sum, i, j;
Triple(int sum, int i, int j) {
this.sum = sum;
this.i = i;
this.j = j;
}
}
}JavaScript solution
matched/originalvar kSmallestPairs = function(nums1, nums2, k) {
let m = nums1.length, n = nums2.length;
let ans = [];
let visited = new Set();
let minHeap = new MinHeap();
minHeap.insert([nums1[0] + nums2[0], 0, 0]);
visited.add(`0,0`);
while (k-- > 0 && minHeap.size() > 0) {
let [sum, i, j] = minHeap.extractMin();
ans.push([nums1[i], nums2[j]]);
if (i + 1 < m && !visited.has(`${i + 1},${j}`)) {
minHeap.insert([nums1[i + 1] + nums2[j], i + 1, j]);
visited.add(`${i + 1},${j}`);
}
if (j + 1 < n && !visited.has(`${i},${j + 1}`)) {
minHeap.insert([nums1[i] + nums2[j + 1], i, j + 1]);
visited.add(`${i},${j + 1}`);
}
}
return ans;
};
class MinHeap {
constructor() {
this.heap = [];
}
size() {
return this.heap.length;
}
insert(val) {
this.heap.push(val);
this.bubbleUp();
}
extractMin() {
if (this.size() === 1) return this.heap.pop();
let min = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown();
return min;
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
let element = this.heap[index];
let parentIndex = Math.floor((index - 1) / 2);
let parent = this.heap[parentIndex];
if (parent[0] <= element[0]) break;
this.heap[index] = parent;
this.heap[parentIndex] = element;
index = parentIndex;
}
}
bubbleDown() {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild[0] < element[0]) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && rightChild[0] < element[0]) ||
(swap !== null && rightChild[0] < leftChild[0])
) {
swap = rightChildIndex;
}
}Python solution
matched/originalimport heapq
class Solution:
def kSmallestPairs(self, nums1, nums2, k):
m, n = len(nums1), len(nums2)
ans = []
visited = set()
minHeap = [(nums1[0] + nums2[0], 0, 0)]
visited.add((0, 0))
while k > 0 and minHeap:
sum_val, i, j = heapq.heappop(minHeap)
ans.append([nums1[i], nums2[j]])
if i + 1 < m and (i + 1, j) not in visited:
heapq.heappush(minHeap, (nums1[i + 1] + nums2[j], i + 1, j))
visited.add((i + 1, j))
if j + 1 < n and (i, j + 1) not in visited:
heapq.heappush(minHeap, (nums1[i] + nums2[j + 1], i, j + 1))
visited.add((i, j + 1))
k -= 1
return ansExplanation
Algorithm
Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар.
Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited.
Повторяйте до получения k пар и пока minHeap не пуст:
Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2].
Добавьте пару (nums1[i], nums2[j]) в ans.
Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap.
Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap.
Верните ans.
😎