Dadas k listas ordenadas de enteros de tamaño n cada una, encuentre el rango más pequeño que incluya al menos un elemento de cada una de las k listas. Si se encuentra más de un rango más pequeño, imprima cualquiera de ellos.
Ejemplo:
Input: K = 3 arr1[] : [4, 7, 9, 12, 15] arr2[] : [0, 8, 10, 14, 20] arr3[] : [6, 12, 16, 30, 50] Output: The smallest range is [6 8] Explanation: Smallest range is formed by number 7 from the first list, 8 from second list and 6 from the third list. Input: k = 3 arr1[] : [4, 7] arr2[] : [1, 2] arr3[] : [20, 40] Output: The smallest range is [2 20] Explanation:The range [2, 20] contains 2, 4, 7, 20 which contains element from all the three arrays.
Enfoque ingenuo:Dada la lista ordenada K, encuentre un rango donde haya al menos un elemento de cada lista. La idea para resolver el problema es muy simple, mantenga k punteros que constituirán los elementos en el rango, tomando el mínimo y el máximo de los k elementos se puede formar el rango. Inicialmente, todos los punteros apuntarán al inicio de todos los k arreglos. Almacene el rango máximo a mínimo. Si se debe minimizar el rango, se debe aumentar el valor mínimo o disminuir el valor máximo. Para disminuir el valor máximo, tenemos que mover nuestro puntero de máximo actual hacia la izquierda y, dado que actualmente estamos en 0, el índice de cada lista, por lo que no podemos mover nuestro puntero hacia la izquierda, por lo tanto, no podemos disminuir el máximo actual. Entonces, la única opción posible para obtener un mejor rango es aumentar el mínimo actual. Para seguir aumentando el valor mínimo,
- Algoritmo:
- Cree un ptr de espacio adicional de longitud k para almacenar los punteros y una variable minrange inicializada a un valor máximo.
- Inicialmente, el índice de cada lista es 0, por lo tanto, inicialice cada elemento de ptr[0..k] a 0, la array ptr almacenará el índice de los elementos en el rango.
- Repita los siguientes pasos hasta que se agote al menos una lista:
- Ahora encuentre el valor mínimo y máximo entre los elementos actuales de toda la lista apuntada por la array ptr[0…k].
- Ahora actualice el rango mínimo si la corriente (máximo-mínimo) es menor que el rango mínimo.
- incrementar el puntero apuntando al elemento mínimo actual.
Implementación:
C++
// C++ program to finds out smallest range that includes
// elements from each of the given sorted lists.
#include <bits/stdc++.h>
using namespace std;
#define N 5
// array for storing the current index of list i
int ptr[501];
// This function takes an k sorted lists in the form of
// 2D array as an argument. It finds out smallest range
// that includes elements from each of the k lists.
void findSmallestRange(int arr[][N], int n, int k)
{
int i, minval, maxval, minrange, minel, maxel, flag, minind;
// initializing to 0 index;
for (i = 0; i <= k; i++)
ptr[i] = 0;
minrange = INT_MAX;
while (1) {
// for maintaining the index of list containing the minimum element
minind = -1;
minval = INT_MAX;
maxval = INT_MIN;
flag = 0;
// iterating over all the list
for (i = 0; i < k; i++) {
// if every element of list[i] is traversed then break the loop
if (ptr[i] == n) {
flag = 1;
break;
}
// find minimum value among all the list elements pointing by the ptr[] array
if (ptr[i] < n && arr[i][ptr[i]] < minval) {
minind = i; // update the index of the list
minval = arr[i][ptr[i]];
}
// find maximum value among all the list elements pointing by the ptr[] array
if (ptr[i] < n && arr[i][ptr[i]] > maxval) {
maxval = arr[i][ptr[i]];
}
}
// if any list exhaust we will not get any better answer, so break the while loop
if (flag)
break;
ptr[minind]++;
// updating the minrange
if ((maxval - minval) < minrange) {
minel = minval;
maxel = maxval;
minrange = maxel - minel;
}
}
printf("The smallest range is [%d, %d]\n", minel, maxel);
}
// Driver program to test above function
int main()
{
int arr[][N] = {
{ 4, 7, 9, 12, 15 },
{ 0, 8, 10, 14, 20 },
{ 6, 12, 16, 30, 50 }
};
int k = sizeof(arr) / sizeof(arr[0]);
findSmallestRange(arr, N, k);
return 0;
}
// This code is contributed by Aditya Krishna Namdeo
Java
// Java program to finds out smallest range that includes
// elements from each of the given sorted lists.
class GFG {
static final int N = 5;
// array for storing the current index of list i
static int ptr[] = new int[501];
// This function takes an k sorted lists in the form of
// 2D array as an argument. It finds out smallest range
// that includes elements from each of the k lists.
static void findSmallestRange(int arr[][], int n, int k)
{
int i, minval, maxval, minrange, minel = 0, maxel = 0, flag, minind;
// initializing to 0 index;
for (i = 0; i <= k; i++) {
ptr[i] = 0;
}
minrange = Integer.MAX_VALUE;
while (true) {
// for maintaining the index of list containing the minimum element
minind = -1;
minval = Integer.MAX_VALUE;
maxval = Integer.MIN_VALUE;
flag = 0;
// iterating over all the list
for (i = 0; i < k; i++) {
// if every element of list[i] is traversed then break the loop
if (ptr[i] == n) {
flag = 1;
break;
}
// find minimum value among all the list elements pointing by the ptr[] array
if (ptr[i] < n && arr[i][ptr[i]] < minval) {
minind = i; // update the index of the list
minval = arr[i][ptr[i]];
}
// find maximum value among all the list elements pointing by the ptr[] array
if (ptr[i] < n && arr[i][ptr[i]] > maxval) {
maxval = arr[i][ptr[i]];
}
}
// if any list exhaust we will not get any better answer, so break the while loop
if (flag == 1) {
break;
}
ptr[minind]++;
// updating the minrange
if ((maxval - minval) < minrange) {
minel = minval;
maxel = maxval;
minrange = maxel - minel;
}
}
System.out.printf("The smallest range is [%d, %d]\n", minel, maxel);
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[][] = {
{ 4, 7, 9, 12, 15 },
{ 0, 8, 10, 14, 20 },
{ 6, 12, 16, 30, 50 }
};
int k = arr.length;
findSmallestRange(arr, N, k);
}
}
// this code contributed by Rajput-Ji
Python
# Python3 program to finds out
# smallest range that includes
# elements from each of the
# given sorted lists.
N = 5
# array for storing the
# current index of list i
ptr = [0 for i in range(501)]
# This function takes an k sorted
# lists in the form of 2D array as
# an argument. It finds out smallest
# range that includes elements from
# each of the k lists.
def findSmallestRange(arr, n, k):
i, minval, maxval, minrange, minel, maxel, flag, minind = 0, 0, 0, 0, 0, 0, 0, 0
# initializing to 0 index
for i in range(k + 1):
ptr[i] = 0
minrange = 10**9
while(1):
# for maintaining the index of list
# containing the minimum element
minind = -1
minval = 10**9
maxval = -10**9
flag = 0
# iterating over all the list
for i in range(k):
# if every element of list[i] is
# traversed then break the loop
if(ptr[i] == n):
flag = 1
break
# find minimum value among all the list
# elements pointing by the ptr[] array
if(ptr[i] < n and arr[i][ptr[i]] < minval):
minind = i # update the index of the list
minval = arr[i][ptr[i]]
# find maximum value among all the
# list elements pointing by the ptr[] array
if(ptr[i] < n and arr[i][ptr[i]] > maxval):
maxval = arr[i][ptr[i]]
# if any list exhaust we will
# not get any better answer,
# so break the while loop
if(flag):
break
ptr[minind] += 1
# updating the minrange
if((maxval-minval) < minrange):
minel = minval
maxel = maxval
minrange = maxel - minel
print("The smallest range is [", minel, maxel, "]")
# Driver code
arr = [
[4, 7, 9, 12, 15],
[0, 8, 10, 14, 20],
[6, 12, 16, 30, 50]
]
k = len(arr)
findSmallestRange(arr, N, k)
# This code is contributed by mohit kumar
C#
// C# program to finds out smallest
// range that includes elements from
// each of the given sorted lists.
using System;
class GFG {
static int N = 5;
// array for storing the current index of list i
static int[] ptr = new int[501];
// This function takes an k sorted
// lists in the form of 2D array as
// an argument. It finds out smallest range
// that includes elements from each of the k lists.
static void findSmallestRange(int[, ] arr,
int n, int k)
{
int i, minval, maxval, minrange,
minel = 0, maxel = 0, flag, minind;
// initializing to 0 index;
for (i = 0; i <= k; i++) {
ptr[i] = 0;
}
minrange = int.MaxValue;
while (true) {
// for maintaining the index of
// list containing the minimum element
minind = -1;
minval = int.MaxValue;
maxval = int.MinValue;
flag = 0;
// iterating over all the list
for (i = 0; i < k; i++) {
// if every element of list[i]
// is traversed then break the loop
if (ptr[i] == n) {
flag = 1;
break;
}
// find minimum value among all the
// list elements pointing by the ptr[] array
if (ptr[i] < n && arr[i, ptr[i]] < minval) {
minind = i; // update the index of the list
minval = arr[i, ptr[i]];
}
// find maximum value among all the
// list elements pointing by the ptr[] array
if (ptr[i] < n && arr[i, ptr[i]] > maxval) {
maxval = arr[i, ptr[i]];
}
}
// if any list exhaust we will
// not get any better answer,
// so break the while loop
if (flag == 1) {
break;
}
ptr[minind]++;
// updating the minrange
if ((maxval - minval) < minrange) {
minel = minval;
maxel = maxval;
minrange = maxel - minel;
}
}
Console.WriteLine("The smallest range is"
+ "[{0}, {1}]\n",
minel, maxel);
}
// Driver code
public static void Main(String[] args)
{
int[, ] arr = {
{ 4, 7, 9, 12, 15 },
{ 0, 8, 10, 14, 20 },
{ 6, 12, 16, 30, 50 }
};
int k = arr.GetLength(0);
findSmallestRange(arr, N, k);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to finds out smallest range that includes
// elements from each of the given sorted lists.
let N = 5;
// array for storing the current index of list i
let ptr=new Array(501);
// This function takes an k sorted lists in the form of
// 2D array as an argument. It finds out smallest range
// that includes elements from each of the k lists.
function findSmallestRange(arr,n,k)
{
let i, minval, maxval, minrange, minel = 0, maxel = 0, flag, minind;
// initializing to 0 index;
for (i = 0; i <= k; i++) {
ptr[i] = 0;
}
minrange = Number.MAX_VALUE;
while (true) {
// for maintaining the index of list containing the minimum element
minind = -1;
minval = Number.MAX_VALUE;
maxval = Number.MIN_VALUE;
flag = 0;
// iterating over all the list
for (i = 0; i < k; i++) {
// if every element of list[i] is traversed then break the loop
if (ptr[i] == n) {
flag = 1;
break;
}
// find minimum value among all the list elements pointing by the ptr[] array
if (ptr[i] < n && arr[i][ptr[i]] < minval) {
minind = i; // update the index of the list
minval = arr[i][ptr[i]];
}
// find maximum value among all the list elements pointing by the ptr[] array
if (ptr[i] < n && arr[i][ptr[i]] > maxval) {
maxval = arr[i][ptr[i]];
}
}
// if any list exhaust we will not get any better answer, so break the while loop
if (flag == 1) {
break;
}
ptr[minind]++;
// updating the minrange
if ((maxval - minval) < minrange) {
minel = minval;
maxel = maxval;
minrange = maxel - minel;
}
}
document.write("The smallest range is ["+minel+", "+maxel+"]<br>");
}
// Driver program to test above function
let arr = [
[4, 7, 9, 12, 15],
[0, 8, 10, 14, 20],
[6, 12, 16, 30, 50]
]
let k = arr.length;
findSmallestRange(arr, N, k);
// This code is contributed by unknown2108
</script>
Producción
The smallest range is [6, 8]
- Análisis de Complejidad:
- Complejidad del tiempo: O(n * k 2 ), para encontrar el máximo y el mínimo en una array de longitud k, el tiempo requerido es O(k), y para recorrer todas las k arrays de longitud n (en el peor de los casos), el tiempo complejidad es O(n*k), entonces la complejidad de tiempo total es O(n*k 2 ).
- Complejidad del espacio: O(k), se requiere una array adicional de longitud k, por lo que la complejidad del espacio es O(k)
Enfoque eficiente : el enfoque sigue siendo el mismo, pero la complejidad del tiempo se puede reducir utilizando min-heap o cola de prioridad . El montón mínimo se puede usar para encontrar el valor máximo y mínimo en tiempo logarítmico o en tiempo log k en lugar de tiempo lineal. El resto del enfoque sigue siendo el mismo.
- Algoritmo:
- cree un montón mínimo para almacenar k elementos, uno de cada array y una variable minrange inicializada a un valor máximo y también mantenga una variable max para almacenar el número entero máximo.
- Inicialmente, coloque el primer elemento de cada elemento de cada lista y almacene el valor máximo en max .
- Repita los siguientes pasos hasta que se agote al menos una lista:
- Para encontrar el valor mínimo o min , use la parte superior o la raíz del montón Min, que es el elemento mínimo.
- Ahora actualice el rango mínimo si la corriente (máximo-mínimo) es menor que el rango mínimo.
- elimine el elemento superior o raíz de la cola de prioridad e inserte el siguiente elemento de la lista que contiene el elemento mínimo y actualice el máximo con el nuevo elemento insertado.
Implementación:
C++
// C++ program to finds out smallest range that includes
// elements from each of the given sorted lists.
#include <bits/stdc++.h>
using namespace std;
#define N 5
// A min heap node
struct MinHeapNode {
// The element to be stored
int element;
// index of the list from which the element is taken
int i;
// index of the next element to be picked from list
int j;
};
// Prototype of a utility function to swap two min heap nodes
void swap(MinHeapNode* x, MinHeapNode* y);
// A class for Min Heap
class MinHeap {
// pointer to array of elements in heap
MinHeapNode* harr;
// size of min heap
int heap_size;
public:
// Constructor: creates a min heap of given size
MinHeap(MinHeapNode a[], int size);
// to heapify a subtree with root at given index
void MinHeapify(int);
// to get index of left child of node at index i
int left(int i) { return (2 * i + 1); }
// to get index of right child of node at index i
int right(int i) { return (2 * i + 2); }
// to get the root
MinHeapNode getMin() { return harr[0]; }
// to replace root with new node x and heapify() new root
void replaceMin(MinHeapNode x)
{
harr[0] = x;
MinHeapify(0);
}
};
// Constructor: Builds a heap from a
// given array a[] of given size
MinHeap::MinHeap(MinHeapNode a[], int size)
{
heap_size = size;
harr = a; // store address of array
int i = (heap_size - 1) / 2;
while (i >= 0) {
MinHeapify(i);
i--;
}
}
// A recursive method to heapify a subtree with root at
// given index. This method assumes that the subtrees
// are already heapified
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l].element < harr[i].element)
smallest = l;
if (r < heap_size && harr[r].element < harr[smallest].element)
smallest = r;
if (smallest != i) {
swap(harr[i], harr[smallest]);
MinHeapify(smallest);
}
}
// This function takes an k sorted lists in the form of
// 2D array as an argument. It finds out smallest range
// that includes elements from each of the k lists.
void findSmallestRange(int arr[][N], int k)
{
// Create a min heap with k heap nodes. Every heap node
// has first element of an list
int range = INT_MAX;
int min = INT_MAX, max = INT_MIN;
int start, end;
MinHeapNode* harr = new MinHeapNode[k];
for (int i = 0; i < k; i++) {
// Store the first element
harr[i].element = arr[i][0];
// index of list
harr[i].i = i;
// Index of next element to be stored
// from list
harr[i].j = 1;
// store max element
if (harr[i].element > max)
max = harr[i].element;
}
// Create the heap
MinHeap hp(harr, k);
// Now one by one get the minimum element from min
// heap and replace it with next element of its list
while (1) {
// Get the minimum element and store it in output
MinHeapNode root = hp.getMin();
// update min
min = hp.getMin().element;
// update range
if (range > max - min + 1) {
range = max - min + 1;
start = min;
end = max;
}
// Find the next element that will replace current
// root of heap. The next element belongs to same
// list as the current root.
if (root.j < N) {
root.element = arr[root.i][root.j];
root.j += 1;
// update max element
if (root.element > max)
max = root.element;
}
// break if we have reached end of any list
else
break;
// Replace root with next element of list
hp.replaceMin(root);
}
cout << "The smallest range is "
<< "["
<< start << " " << end << "]" << endl;
;
}
// Driver program to test above functions
int main()
{
int arr[][N] = {
{ 4, 7, 9, 12, 15 },
{ 0, 8, 10, 14, 20 },
{ 6, 12, 16, 30, 50 }
};
int k = sizeof(arr) / sizeof(arr[0]);
findSmallestRange(arr, k);
return 0;
}
Java
// Java program to find out smallest
// range that includes elements from
// each of the given sorted lists.
class GFG {
// A min heap node
static class Node {
// The element to be stored
int ele;
// index of the list from which
// the element is taken
int i;
// index of the next element
// to be picked from list
int j;
Node(int a, int b, int c)
{
this.ele = a;
this.i = b;
this.j = c;
}
}
// A class for Min Heap
static class MinHeap {
Node[] harr; // array of elements in heap
int size; // size of min heap
// Constructor: creates a min heap
// of given size
MinHeap(Node[] arr, int size)
{
this.harr = arr;
this.size = size;
int i = (size - 1) / 2;
while (i >= 0) {
MinHeapify(i);
i--;
}
}
// to get index of left child
// of node at index i
int left(int i)
{
return 2 * i + 1;
}
// to get index of right child
// of node at index i
int right(int i)
{
return 2 * i + 2;
}
// to heapify a subtree with
// root at given index
void MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int small = i;
if (l < size && harr[l].ele < harr[i].ele)
small = l;
if (r < size && harr[r].ele < harr[small].ele)
small = r;
if (small != i) {
swap(small, i);
MinHeapify(small);
}
}
void swap(int i, int j)
{
Node temp = harr[i];
harr[i] = harr[j];
harr[j] = temp;
}
// to get the root
Node getMin()
{
return harr[0];
}
// to replace root with new node x
// and heapify() new root
void replaceMin(Node x)
{
harr[0] = x;
MinHeapify(0);
}
}
// This function takes an k sorted lists
// in the form of 2D array as an argument.
// It finds out smallest range that includes
// elements from each of the k lists.
static void findSmallestRange(int[][] arr, int k)
{
int range = Integer.MAX_VALUE;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int start = -1, end = -1;
int n = arr[0].length;
// Create a min heap with k heap nodes.
// Every heap node has first element of an list
Node[] arr1 = new Node[k];
for (int i = 0; i < k; i++) {
Node node = new Node(arr[i][0], i, 1);
arr1[i] = node;
// store max element
max = Math.max(max, node.ele);
}
// Create the heap
MinHeap mh = new MinHeap(arr1, k);
// Now one by one get the minimum element
// from min heap and replace it with
// next element of its list
while (true) {
// Get the minimum element and
// store it in output
Node root = mh.getMin();
// update min
min = root.ele;
// update range
if (range > max - min + 1) {
range = max - min + 1;
start = min;
end = max;
}
// Find the next element that will
// replace current root of heap.
// The next element belongs to same
// list as the current root.
if (root.j < n) {
root.ele = arr[root.i][root.j];
root.j++;
// update max element
if (root.ele > max)
max = root.ele;
}
// break if we have reached
// end of any list
else
break;
// Replace root with next element of list
mh.replaceMin(root);
}
System.out.print("The smallest range is [" + start + " " + end + "]");
}
// Driver Code
public static void main(String[] args)
{
int arr[][] = { { 4, 7, 9, 12, 15 },
{ 0, 8, 10, 14, 20 },
{ 6, 12, 16, 30, 50 } };
int k = arr.length;
findSmallestRange(arr, k);
}
}
// This code is contributed by nobody_cares
C#
// C# program to find out smallest
// range that includes elements from
// each of the given sorted lists.
using System;
using System.Collections.Generic;
class GFG {
// A min heap node
public class Node {
// The element to be stored
public int ele;
// index of the list from which
// the element is taken
public int i;
// index of the next element
// to be picked from list
public int j;
public Node(int a, int b, int c)
{
this.ele = a;
this.i = b;
this.j = c;
}
}
// A class for Min Heap
public class MinHeap {
// array of elements in heap
public Node[] harr;
// size of min heap
public int size;
// Constructor: creates a min heap
// of given size
public MinHeap(Node[] arr, int size)
{
this.harr = arr;
this.size = size;
int i = (size - 1) / 2;
while (i >= 0) {
MinHeapify(i);
i--;
}
}
// to get index of left child
// of node at index i
int left(int i)
{
return 2 * i + 1;
}
// to get index of right child
// of node at index i
int right(int i)
{
return 2 * i + 2;
}
// to heapify a subtree with
// root at given index
void MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int small = i;
if (l < size && harr[l].ele < harr[i].ele)
small = l;
if (r < size && harr[r].ele < harr[small].ele)
small = r;
if (small != i) {
swap(small, i);
MinHeapify(small);
}
}
void swap(int i, int j)
{
Node temp = harr[i];
harr[i] = harr[j];
harr[j] = temp;
}
// to get the root
public Node getMin()
{
return harr[0];
}
// to replace root with new node x
// and heapify() new root
public void replaceMin(Node x)
{
harr[0] = x;
MinHeapify(0);
}
}
// This function takes an k sorted lists
// in the form of 2D array as an argument.
// It finds out smallest range that includes
// elements from each of the k lists.
static void findSmallestRange(int[, ] arr, int k)
{
int range = int.MaxValue;
int min = int.MaxValue;
int max = int.MinValue;
int start = -1, end = -1;
int n = arr.GetLength(0);
// Create a min heap with k heap nodes.
// Every heap node has first element of an list
Node[] arr1 = new Node[k];
for (int i = 0; i < k; i++) {
Node node = new Node(arr[i, 0], i, 1);
arr1[i] = node;
// store max element
max = Math.Max(max, node.ele);
}
// Create the heap
MinHeap mh = new MinHeap(arr1, k);
// Now one by one get the minimum element
// from min heap and replace it with
// next element of its list
while (true) {
// Get the minimum element and
// store it in output
Node root = mh.getMin();
// update min
min = root.ele;
// update range
if (range > max - min + 1) {
range = max - min + 1;
start = min;
end = max;
}
// Find the next element that will
// replace current root of heap.
// The next element belongs to same
// list as the current root.
if (root.j < n) {
root.ele = arr[root.i, root.j];
root.j++;
// update max element
if (root.ele > max)
max = root.ele;
}
else
break; // break if we have reached
// end of any list
// Replace root with next element of list
mh.replaceMin(root);
}
Console.Write("The smallest range is [" + start + " " + end + "]");
}
// Driver Code
public static void Main(String[] args)
{
int[, ] arr = { { 4, 7, 9, 12, 15 },
{ 0, 8, 10, 14, 20 },
{ 6, 12, 16, 30, 50 } };
int k = arr.GetLength(0);
findSmallestRange(arr, k);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find out smallest
// range that includes elements from
// each of the given sorted lists.
class Node
{
constructor(a, b, c)
{
this.ele = a;
this.i = b;
this.j = c;
}
}
// A class for Min Heap
class MinHeap
{
// Array of elements in heap
harr;
// Size of min heap
size;
// Constructor: creates a min heap
// of given size
constructor(arr,size)
{
this.harr = arr;
this.size = size;
let i = Math.floor((size - 1) / 2);
while (i >= 0)
{
this.MinHeapify(i);
i--;
}
}
// To get index of left child
// of node at index i
left(i)
{
return 2 * i + 1;
}
// To get index of right child
// of node at index i
right(i)
{
return 2 * i + 2;
}
// To heapify a subtree with
// root at given index
MinHeapify(i)
{
let l = this.left(i);
let r = this.right(i);
let small = i;
if (l < this.size &&
this.harr[l].ele <
this.harr[i].ele)
small = l;
if (r < this.size &&
this.harr[r].ele <
this.harr[small].ele)
small = r;
if (small != i)
{
this.swap(small, i);
this.MinHeapify(small);
}
}
swap(i, j)
{
let temp = this.harr[i];
this.harr[i] = this.harr[j];
this.harr[j] = temp;
}
// To get the root
getMin()
{
return this.harr[0];
}
// To replace root with new node x
// and heapify() new root
replaceMin(x)
{
this.harr[0] = x;
this.MinHeapify(0);
}
}
// This function takes an k sorted lists
// in the form of 2D array as an argument.
// It finds out smallest range that includes
// elements from each of the k lists.
function findSmallestRange(arr, k)
{
let range = Number.MAX_VALUE;
let min = Number.MAX_VALUE;
let max = Number.MIN_VALUE;
let start = -1, end = -1;
let n = arr[0].length;
// Create a min heap with k heap nodes.
// Every heap node has first element of an list
let arr1 = new Array(k);
for(let i = 0; i < k; i++)
{
let node = new Node(arr[i][0], i, 1);
arr1[i] = node;
// Store max element
max = Math.max(max, node.ele);
}
// Create the heap
let mh = new MinHeap(arr1, k);
// Now one by one get the minimum element
// from min heap and replace it with
// next element of its list
while (true)
{
// Get the minimum element and
// store it in output
let root = mh.getMin();
// Update min
min = root.ele;
// Update range
if (range > max - min + 1)
{
range = max - min + 1;
start = min;
end = max;
}
// Find the next element that will
// replace current root of heap.
// The next element belongs to same
// list as the current root.
if (root.j < n)
{
root.ele = arr[root.i][root.j];
root.j++;
// Update max element
if (root.ele > max)
max = root.ele;
}
// Break if we have reached
// end of any list
else
break;
// Replace root with next element of list
mh.replaceMin(root);
}
document.write("The smallest range is [" +
start + " " + end + "]");
}
// Driver Code
let arr = [ [ 4, 7, 9, 12, 15 ],
[ 0, 8, 10, 14, 20 ],
[ 6, 12, 16, 30, 50 ] ];
let k = arr.length;
findSmallestRange(arr, k);
// This code is contributed by rag2127
</script>
Producción
The smallest range is [6 8]
- Análisis de Complejidad:
- Complejidad del tiempo: O(n * k *log k).
Para encontrar el máximo y el mínimo en un Min Heap de longitud k, el tiempo requerido es O(log k), y para recorrer todos los k arreglos de longitud n (en el peor de los casos), la complejidad del tiempo es O(n*k) , entonces la complejidad temporal total es O(n * k *log k). - Complejidad espacial: O(k).
La cola de prioridad almacenará k elementos, por lo que la complejidad espacial de O(k)
- Complejidad del tiempo: O(n * k *log k).
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA