632. Smallest Range Covering Elements from K Lists
leetcode hard
#array#csharp#hard#heap#leetcode#math#queue#sort
Task
У вас есть k списков отсортированных целых чисел в неубывающем порядке. Найдите наименьший диапазон, в который входит хотя бы одно число из каждого из k списков. Мы определяем, что диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c, если b - a == d - c.
Пример:
Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
C# solution
matched/originalusing System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int[] SmallestRange(IList<IList<int>> nums) {
var minHeap = new PriorityQueue<Element, int>();
int maxValue = int.MinValue;
for (int i = 0; i < nums.Count; i++) {
minHeap.Enqueue(new Element(nums[i][0], i, 0), nums[i][0]);
maxValue = Math.Max(maxValue, nums[i][0]);
}
int rangeStart = 0, rangeEnd = int.MaxValue;
while (minHeap.Count == nums.Count) {
var minElement = minHeap.Dequeue();
if (maxValue - minElement.Value < rangeEnd - rangeStart) {
rangeStart = minElement.Value;
rangeEnd = maxValue;
}
if (minElement.Col + 1 < nums[minElement.Row].Count) {
int newValue = nums[minElement.Row][minElement.Col + 1];
minHeap.Enqueue(new Element(newValue, minElement.Row, minElement.Col + 1), newValue);
maxValue = Math.Max(maxValue, newValue);
}
}
return new int[] { rangeStart, rangeEnd };
}
}
public class Element {
public int Value { get; }
public int Row { get; }
public int Col { get; }
public Element(int value, int row, int col) {
Value = value;
Row = row;
Col = col;
}
}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 vector<int>& SmallestRange(IList<vector<int>> nums) {
var minHeap = new PriorityQueue<Element, int>();
int maxValue = int.MinValue;
for (int i = 0; i < nums.size(); i++) {
minHeap.Enqueue(new Element(nums[i][0], i, 0), nums[i][0]);
maxValue = max(maxValue, nums[i][0]);
}
int rangeStart = 0, rangeEnd = int.MaxValue;
while (minHeap.size() == nums.size()) {
var minElement = minHeap.Dequeue();
if (maxValue - minElement.Value < rangeEnd - rangeStart) {
rangeStart = minElement.Value;
rangeEnd = maxValue;
}
if (minElement.Col + 1 < nums[minElement.Row].size()) {
int newValue = nums[minElement.Row][minElement.Col + 1];
minHeap.Enqueue(new Element(newValue, minElement.Row, minElement.Col + 1), newValue);
maxValue = max(maxValue, newValue);
}
}
return new int[] { rangeStart, rangeEnd };
}
}
public class Element {
public int Value { get; }
public int Row { get; }
public int Col { get; }
public Element(int value, int row, int col) {
Value = value;
Row = row;
Col = col;
}
}Java solution
matched/originalimport java.util.PriorityQueue;
public class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<Element> minHeap = new PriorityQueue<>((a, b) -> a.value - b.value);
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < nums.size(); i++) {
int value = nums.get(i).get(0);
minHeap.add(new Element(value, i, 0));
maxValue = Math.max(maxValue, value);
}
int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;
while (minHeap.size() == nums.size()) {
Element minElement = minHeap.poll();
if (maxValue - minElement.value < rangeEnd - rangeStart) {
rangeStart = minElement.value;
rangeEnd = maxValue;
}
if (minElement.col + 1 < nums.get(minElement.row).size()) {
int value = nums.get(minElement.row).get(minElement.col + 1);
minHeap.add(new Element(value, minElement.row, minElement.col + 1));
maxValue = Math.max(maxValue, value);
}
}
return new int[]{rangeStart, rangeEnd};
}
}
class Element {
int value, row, col;
Element(int value, int row, int col) {
this.value = value;
this.row = row;
this.col = col;
}
}Python solution
matched/originalfrom heapq import heappop, heappush
def smallestRange(nums):
min_heap = []
max_value = float('-inf')
for i in range(len(nums)):
heappush(min_heap, (nums[i][0], i, 0))
max_value = max(max_value, nums[i][0])
range_start, range_end = float('-inf'), float('inf')
while len(min_heap) == len(nums):
min_value, row, col = heappop(min_heap)
if max_value - min_value < range_end - range_start:
range_start, range_end = min_value, max_value
if col + 1 < len(nums[row]):
heappush(min_heap, (nums[row][col + 1], row, col + 1))
max_value = max(max_value, nums[row][col + 1])
return [range_start, range_end]Go solution
matched/originalpackage main
import (
"container/heap"
"fmt"
"math"
)
type Element struct {
value int
row int
col int
}
type MinHeap []Element
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].value < h[j].value }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(Element))
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func smallestRange(nums [][]int) []int {
minHeap := &MinHeap{}
heap.Init(minHeap)
maxValue := math.MinInt64
for i := 0; i < len(nums); i++ {
heap.Push(minHeap, Element{value: nums[i][0], row: i, col: 0})
if nums[i][0] > maxValue {
maxValue = nums[i][0]
}
}
rangeStart, rangeEnd := 0, math.MaxInt64
for minHeap.Len() == len(nums) {
minElement := heap.Pop(minHeap).(Element)
if maxValue-minElement.value < rangeEnd-rangeStart {
rangeStart, rangeEnd = minElement.value, maxValue
}
if minElement.col+1 < len(nums[minElement.row]) {
newValue := nums[minElement.row][minElement.col+1]
heap.Push(minHeap, Element{value: newValue, row: minElement.row, col: minElement.col + 1})
if newValue > maxValue {
maxValue = newValue
}
}
}
return []int{rangeStart, rangeEnd}
}Explanation
Algorithm
Инициализация и сбор всех начальных элементов
Создайте массив для хранения текущих индексов каждого списка и используйте минимальную кучу для отслеживания текущих минимальных элементов из каждого списка.
Нахождение минимального диапазона
Используйте кучу для извлечения минимального элемента и обновления текущего диапазона. Обновляйте максимальный элемент в текущем диапазоне при добавлении новых элементов.
Проверка и обновление диапазона
Продолжайте обновлять кучу и диапазон, пока возможно. Завершите, когда один из списков исчерпан.
😎