Menor faixa com elementos de k listas classificadas
Dado uma matriz inteira 2D arr [] [] de ordem k * n onde está cada linha classificado em ordem crescente. Sua tarefa é encontrar o menor alcance que inclui pelo menos um elemento de cada um dos K listas. Se mais de um desses intervalos forem encontrados, retorne o primeiro.
Exemplos:
Entrada: arr [] = [[4 7 9 12 15]
[0 8 10 14 20]
[6 12 16 30 50]]
Saída: 6 8
Explicação: O menor intervalo é formado pelo número 7 da primeira lista 8 da segunda lista e 6 da terceira lista.Entrada: arr [] [] = [[2 4]
[1 7]
[20 40]]
Saída: 4 20
Explicação: O intervalo [4 20] contém 4 7 20, que contém elemento de todas as três matrizes.
Tabela de conteúdo
- [Abordagem ingênua] - Usando K Pontenters - O (n k^2) tempo e o (k) espaço
- [Abordagem melhor] usando dois ponteiros - o (n*k log (n*k)) tempo e o (n*k) espaço
- [Abordagem eficiente] - Usando o tempo Min Heap - O (N K Log K) e O (k)
[Abordagem ingênua] - Usando K Pontenters - O (n k^2) tempo e o (k) espaço
A idéia é manter K ponteiros um para cada lista começando no índice 0. Em cada etapa, tome o min e max dos elementos K atuais para formar um intervalo. Para minimizar o intervalo devemos Aumente o valor mínimo Como não podemos diminuir o máximo (todos os ponteiros começam em 0). Então mova o ponteiro da lista que tem o Mínimo atual e atualize o intervalo. Repita até que uma lista esteja esgotada.
Implementação passo a passo:
- Crie uma lista de ponteiros um para cada lista de entrada, tudo começando no índice 0.
- Repita o processo Até que um dos ponteiros chegue ao final de sua lista.
- A cada passo Escolha os elementos atuais apontado por todos os ponteiros.
- Encontre o Mínimo e máximo entre esses elementos.
- Calcule o intervalo usando os valores MIN e MAX.
- Se esse intervalo for menor do que a melhor atualização anterior da resposta.
- Avance o ponteiro da lista que tinha o elemento mínimo.
- Pare quando qualquer lista estiver esgotada e retorne o melhor alcance encontrado.
// C++ program to find the smallest range // that includes at least one element from // each of the k sorted lists using k pointers #include #include #include using namespace std ; vector < int > findSmallestRange ( vector < vector < int >>& arr ) { int k = arr . size (); int n = arr [ 0 ]. size (); // Pointers for each of the k rows vector < int > ptr ( k 0 ); int minRange = INT_MAX ; int start = -1 end = -1 ; while ( true ) { int minVal = INT_MAX ; int maxVal = INT_MIN ; int minRow = -1 ; // Traverse all k rows to get current min and max for ( int i = 0 ; i < k ; i ++ ) { // If any list is exhausted stop the loop if ( ptr [ i ] == n ) { return { start end }; } // Track min value and its row index if ( arr [ i ][ ptr [ i ]] < minVal ) { minVal = arr [ i ][ ptr [ i ]]; minRow = i ; } // Track current max value if ( arr [ i ][ ptr [ i ]] > maxVal ) { maxVal = arr [ i ][ ptr [ i ]]; } } // Update the result range if a // smaller range is found if ( maxVal - minVal < minRange ) { minRange = maxVal - minVal ; start = minVal ; end = maxVal ; } // Move the pointer of the // row with minimum value ptr [ minRow ] ++ ; } return { start end }; } int main () { vector < vector < int >> arr = { { 4 7 9 12 15 } { 0 8 10 14 20 } { 6 12 16 30 50 } }; vector < int > res = findSmallestRange ( arr ); cout < < res [ 0 ] < < ' ' < < res [ 1 ]; return 0 ; }
Java // Java program to find the smallest range import java.util.* ; class GfG { static ArrayList < Integer > findSmallestRange ( int [][] arr ) { int k = arr . length ; int n = arr [ 0 ] . length ; // Pointers for each of the k rows int [] ptr = new int [ k ] ; int minRange = Integer . MAX_VALUE ; int start = - 1 end = - 1 ; while ( true ) { int minVal = Integer . MAX_VALUE ; int maxVal = Integer . MIN_VALUE ; int minRow = - 1 ; // Traverse all k rows to get current min and max for ( int i = 0 ; i < k ; i ++ ) { // If any list is exhausted stop the loop if ( ptr [ i ] == n ) { ArrayList < Integer > result = new ArrayList <> (); result . add ( start ); result . add ( end ); return result ; } // Track min value and its row index if ( arr [ i ][ ptr [ i ]] < minVal ) { minVal = arr [ i ][ ptr [ i ]] ; minRow = i ; } // Track current max value if ( arr [ i ][ ptr [ i ]] > maxVal ) { maxVal = arr [ i ][ ptr [ i ]] ; } } // Update the result range if a smaller range is found if ( maxVal - minVal < minRange ) { minRange = maxVal - minVal ; start = minVal ; end = maxVal ; } // Move the pointer of the row with minimum value ptr [ minRow ]++ ; } } public static void main ( String [] args ) { int [][] arr = { { 4 7 9 12 15 } { 0 8 10 14 20 } { 6 12 16 30 50 } }; ArrayList < Integer > res = findSmallestRange ( arr ); System . out . println ( res . get ( 0 ) + ' ' + res . get ( 1 )); } }
Python # Python program to find the smallest range def findSmallestRange ( arr ): k = len ( arr ) n = len ( arr [ 0 ]) # Pointers for each of the k rows ptr = [ 0 ] * k min_range = float ( 'inf' ) start = - 1 end = - 1 while True : min_val = float ( 'inf' ) max_val = float ( '-inf' ) min_row = - 1 # Traverse all k rows to get current min and max for i in range ( k ): # If any list is exhausted stop the loop if ptr [ i ] == n : return [ start end ] # Track min value and its row index if arr [ i ][ ptr [ i ]] < min_val : min_val = arr [ i ][ ptr [ i ]] min_row = i # Track current max value if arr [ i ][ ptr [ i ]] > max_val : max_val = arr [ i ][ ptr [ i ]] # Update the result range if a smaller range is found if max_val - min_val < min_range : min_range = max_val - min_val start = min_val end = max_val # Move the pointer of the row with minimum value ptr [ min_row ] += 1 if __name__ == '__main__' : arr = [ [ 4 7 9 12 15 ] [ 0 8 10 14 20 ] [ 6 12 16 30 50 ] ] res = findSmallestRange ( arr ) print ( res [ 0 ] res [ 1 ])
C# using System ; using System.Collections.Generic ; class GfG { static List < int > findSmallestRange ( int [] arr ) { int k = arr . GetLength ( 0 ); int n = arr . GetLength ( 1 ); // Pointers for each of the k rows int [] ptr = new int [ k ]; int minRange = int . MaxValue ; int start = - 1 end = - 1 ; while ( true ) { int minVal = int . MaxValue ; int maxVal = int . MinValue ; int minRow = - 1 ; // Traverse all k rows to get current min and max for ( int i = 0 ; i < k ; i ++ ) { // If any list is exhausted stop the loop if ( ptr [ i ] == n ) { return new List < int > { start end }; } int current = arr [ i ptr [ i ]]; if ( current < minVal ) { minVal = current ; minRow = i ; } if ( current > maxVal ) { maxVal = current ; } } // Update the result range if a smaller range is found if ( maxVal - minVal < minRange ) { minRange = maxVal - minVal ; start = minVal ; end = maxVal ; } // Move the pointer of the row with minimum value ptr [ minRow ] ++ ; } } public static void Main ( string [] args ) { int [] arr = { { 4 7 9 12 15 } { 0 8 10 14 20 } { 6 12 16 30 50 } }; List < int > res = findSmallestRange ( arr ); Console . WriteLine ( res [ 0 ] + ' ' + res [ 1 ]); } }
JavaScript // JavaScript program to find the smallest range function findSmallestRange ( arr ) { let k = arr . length ; let n = arr [ 0 ]. length ; // Pointers for each of the k rows let ptr = new Array ( k ). fill ( 0 ); let minRange = Infinity ; let start = - 1 end = - 1 ; while ( true ) { let minVal = Infinity ; let maxVal = - Infinity ; let minRow = - 1 ; // Traverse all k rows to get current min and max for ( let i = 0 ; i < k ; i ++ ) { // If any list is exhausted stop the loop if ( ptr [ i ] === n ) { return [ start end ]; } // Track min value and its row index if ( arr [ i ][ ptr [ i ]] < minVal ) { minVal = arr [ i ][ ptr [ i ]]; minRow = i ; } // Track current max value if ( arr [ i ][ ptr [ i ]] > maxVal ) { maxVal = arr [ i ][ ptr [ i ]]; } } // Update the result range if a smaller range is found if ( maxVal - minVal < minRange ) { minRange = maxVal - minVal ; start = minVal ; end = maxVal ; } // Move the pointer of the row with minimum value ptr [ minRow ] ++ ; } } const arr = [ [ 4 7 9 12 15 ] [ 0 8 10 14 20 ] [ 6 12 16 30 50 ] ]; const res = findSmallestRange ( arr ); console . log ( res [ 0 ] + ' ' + res [ 1 ]);
Saída
6 8
[Abordagem melhor] usando dois ponteiros - o (n*k log (n*k)) tempo e o (n*k) espaço
C++A idéia é encontrar o menor problema de alcance, transformando -o em um problema de janela deslizante em uma lista mesclada e classificada de todos os elementos das listas de entrada. Cada elemento é armazenado junto com seu índice de lista original para rastrear sua fonte. Depois de classificar a lista combinada por valor dois ponteiros (
lefteright) são usados para definir uma janela que se move pela lista. À medida que a janela expande um mapa de frequência rastreia quantas listas exclusivas são representadas. Quando a janela inclui pelo menos um número de cada lista, o algoritmo tenta encolhê -lo da esquerda para encontrar um intervalo válido menor. O menor intervalo encontrado durante esse processo é retornado como resultado.
#include using namespace std ; vector < int > findSmallestRange ( vector < vector < int >>& arr ) { int k = arr . size (); // Stores the current index for each list vector < int > pointers ( k 0 ); // Stores the current smallest range vector < int > smallestRange = { 0 INT_MAX }; while ( true ) { int currentMin = INT_MAX currentMax = INT_MIN ; int minListIndex = -1 ; // Find the minimum and maximum among current elements of all lists for ( int i = 0 ; i < k ; i ++ ) { int value = arr [ i ][ pointers [ i ]]; if ( value < currentMin ) { currentMin = value ; minListIndex = i ; } if ( value > currentMax ) { currentMax = value ; } } // Update the smallest range if this one is smaller if ( currentMax - currentMin < smallestRange [ 1 ] - smallestRange [ 0 ]) { smallestRange [ 0 ] = currentMin ; smallestRange [ 1 ] = currentMax ; } // Move the pointer in the list that had the minimum value pointers [ minListIndex ] ++ ; // If that list is exhausted break the loop if ( pointers [ minListIndex ] == arr [ minListIndex ]. size ()) break ; } return smallestRange ; } // Driver code int main () { vector < vector < int >> arr = { { 4 7 9 12 15 } { 0 8 10 14 20 } { 6 12 16 30 50 } }; vector < int > result = findSmallestRange ( arr ); cout < < result [ 0 ] < < ' ' < < result [ 1 ]; return 0 ; }
Java import java.util.* ; class GfG { // Function to find the smallest range public static ArrayList < Integer > findSmallestRange ( int [][] arr ) { int k = arr . length ; // Number of lists // Stores the current index for each list int [] pointers = new int [ k ] ; // Stores the current smallest range ArrayList < Integer > smallestRange = new ArrayList <> ( Arrays . asList ( 0 Integer . MAX_VALUE )); // Continue the loop until one list is exhausted while ( true ) { int currentMin = Integer . MAX_VALUE currentMax = Integer . MIN_VALUE ; int minListIndex = - 1 ; // Find the minimum and maximum among current elements of all lists for ( int i = 0 ; i < k ; i ++ ) { int value = arr [ i ][ pointers [ i ]] ; // Update the current minimum if ( value < currentMin ) { currentMin = value ; minListIndex = i ; } // Update the current maximum if ( value > currentMax ) { currentMax = value ; } } // Update the smallest range if this one is smaller if ( currentMax - currentMin < smallestRange . get ( 1 ) - smallestRange . get ( 0 )) { smallestRange . set ( 0 currentMin ); smallestRange . set ( 1 currentMax ); } // Move the pointer in the list that had the minimum value pointers [ minListIndex ]++ ; // If that list is exhausted break the loop if ( pointers [ minListIndex ] == arr [ minListIndex ] . length ) break ; } return smallestRange ; // Return the result as ArrayList } // 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 } }; ArrayList < Integer > result = findSmallestRange ( arr ); System . out . println ( result . get ( 0 ) + ' ' + result . get ( 1 )); } }
Python def findSmallestRange ( arr ): k = len ( arr ) # Number of lists # Stores the current index for each list pointers = [ 0 ] * k # Stores the current smallest range smallestRange = [ 0 float ( 'inf' )] # Continue the loop until one list is exhausted while True : currentMin = float ( 'inf' ) currentMax = - float ( 'inf' ) minListIndex = - 1 # Find the minimum and maximum among current elements of all lists for i in range ( k ): value = arr [ i ][ pointers [ i ]] # Update the current minimum if value < currentMin : currentMin = value minListIndex = i # Update the current maximum if value > currentMax : currentMax = value # Update the smallest range if this one is smaller if currentMax - currentMin < smallestRange [ 1 ] - smallestRange [ 0 ]: smallestRange [ 0 ] = currentMin smallestRange [ 1 ] = currentMax # Move the pointer in the list that had the minimum value pointers [ minListIndex ] += 1 # If that list is exhausted break the loop if pointers [ minListIndex ] == len ( arr [ minListIndex ]): break return smallestRange # Return the result as a list # Driver code if __name__ == '__main__' : arr = [ [ 4 7 9 12 15 ] [ 0 8 10 14 20 ] [ 6 12 16 30 50 ] ] result = findSmallestRange ( arr ) print ( result [ 0 ] result [ 1 ])
C# using System ; using System.Collections.Generic ; class GfG { // Function to find the smallest range public static List < int > findSmallestRange ( int [] arr ) { int k = arr . GetLength ( 0 ); // Number of lists (rows) // Stores the current index for each list (row) int [] pointers = new int [ k ]; // Stores the current smallest range List < int > smallestRange = new List < int > { 0 int . MaxValue }; // Continue the loop until one list is exhausted while ( true ) { int currentMin = int . MaxValue currentMax = int . MinValue ; int minListIndex = - 1 ; // Find the minimum and maximum among current elements // of all lists for ( int i = 0 ; i < k ; i ++ ) { int value = arr [ i pointers [ i ]]; // Update the current minimum if ( value < currentMin ) { currentMin = value ; minListIndex = i ; } // Update the current maximum if ( value > currentMax ) { currentMax = value ; } } // Update the smallest range if this one is smaller if ( currentMax - currentMin < smallestRange [ 1 ] - smallestRange [ 0 ]) { smallestRange [ 0 ] = currentMin ; smallestRange [ 1 ] = currentMax ; } // Move the pointer in the list that had the minimum value pointers [ minListIndex ] ++ ; // If that list is exhausted break the loop if ( pointers [ minListIndex ] == arr . GetLength ( 1 )) break ; } return smallestRange ; // Return the result as List } // 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 } }; List < int > result = findSmallestRange ( arr ); Console . WriteLine ( result [ 0 ] + ' ' + result [ 1 ]); } }
JavaScript function findSmallestRange ( arr ) { const k = arr . length ; // Number of lists // Stores the current index for each list let pointers = new Array ( k ). fill ( 0 ); // Stores the current smallest range let smallestRange = [ 0 Number . MAX_VALUE ]; // Continue the loop until one list is exhausted while ( true ) { let currentMin = Number . MAX_VALUE currentMax = - Number . MAX_VALUE ; let minListIndex = - 1 ; // Find the minimum and maximum among current elements of all lists for ( let i = 0 ; i < k ; i ++ ) { const value = arr [ i ][ pointers [ i ]]; // Update the current minimum if ( value < currentMin ) { currentMin = value ; minListIndex = i ; } // Update the current maximum if ( value > currentMax ) { currentMax = value ; } } // Update the smallest range if this one is smaller if ( currentMax - currentMin < smallestRange [ 1 ] - smallestRange [ 0 ]) { smallestRange [ 0 ] = currentMin ; smallestRange [ 1 ] = currentMax ; } // Move the pointer in the list that had the minimum value pointers [ minListIndex ] ++ ; // If that list is exhausted break the loop if ( pointers [ minListIndex ] === arr [ minListIndex ]. length ) break ; } return smallestRange ; // Return the result as an array } // Driver code const arr = [ [ 4 7 9 12 15 ] [ 0 8 10 14 20 ] [ 6 12 16 30 50 ] ]; const result = findSmallestRange ( arr ); console . log ( result [ 0 ] result [ 1 ]);
Saída
6 8
[Abordagem eficiente] - Usando o tempo Min Heap - O (N K Log K) e O (k)
Min-heap Pode ser usado para encontrar o valor mínimo no tempo logarítmico ou no registro K, em vez do tempo linear. Para encontrar o valor máximo, inicializamos o valor máximo de todos os 0 índices inicialmente. Para o restante dos valores máximos no loop, simplesmente comparamos o valor máximo atual com o próximo item da lista da qual o Min Item está sendo removido. O restante da abordagem permanece o mesmo.
Implementação passo a passo:
- Min-heap Pode ser usado para encontrar o valor mínimo no tempo logarítmico ou no registro K, em vez do tempo linear. Para encontrar o valor máximo, inicializamos o valor máximo de todos os 0 índices inicialmente. Para o restante dos valores máximos no loop, simplesmente comparamos o valor máximo atual com o próximo item da lista da qual o Min Item está sendo removido. O restante da abordagem permanece o mesmo.
Crie um min-heap para armazenar K elementos um de cada matriz e uma variável minrange inicializado com um valor máximo e também mantenha uma variável máx Para armazenar o número inteiro máximo.
- Min-heap Pode ser usado para encontrar o valor mínimo no tempo logarítmico ou no registro K, em vez do tempo linear. Para encontrar o valor máximo, inicializamos o valor máximo de todos os 0 índices inicialmente. Para o restante dos valores máximos no loop, simplesmente comparamos o valor máximo atual com o próximo item da lista da qual o Min Item está sendo removido. O restante da abordagem permanece o mesmo.
Inicialmente coloque o primeiro elemento de cada lista e armazene o valor máximo em máx .
- Min-heap Pode ser usado para encontrar o valor mínimo no tempo logarítmico ou no registro K, em vez do tempo linear. Para encontrar o valor máximo, inicializamos o valor máximo de todos os 0 índices inicialmente. Para o restante dos valores máximos no loop, simplesmente comparamos o valor máximo atual com o próximo item da lista da qual o Min Item está sendo removido. O restante da abordagem permanece o mesmo.
Repita as etapas a seguir até que pelo menos uma lista escapasse:
- Encontre o valor mínimo ou min Use a parte superior ou raiz da pilha min, que é o elemento mínimo.
- Agora atualize o minrange Se o atual (max-min) for menor que minrange .
- Remova o elemento superior ou raiz da fila de prioridade Insira o próximo elemento da lista que contém o elemento min
- Atualize o máximo com o novo elemento inserido se o novo elemento for maior que o máximo anterior.
C++ Java #include
Python import java.util.* ; // Class to represent elements in the heap class Node implements Comparable < Node > { int val row col ; Node ( int val int row int col ) { this . val = val ; this . row = row ; this . col = col ; } // For min-heap based on value public int compareTo ( Node other ) { return this . val - other . val ; } } class GfG { // Function to find the smallest range static ArrayList < Integer > findSmallestRange ( int [][] arr ) { int k = arr . length ; int n = arr [ 0 ] . length ; PriorityQueue < Node > pq = new PriorityQueue <> (); int maxVal = Integer . MIN_VALUE ; // Push the first element of each list into the min-heap for ( int i = 0 ; i < k ; i ++ ) { pq . add ( new Node ( arr [ i ][ 0 ] i 0 )); maxVal = Math . max ( maxVal arr [ i ][ 0 ] ); } int minRange = Integer . MAX_VALUE minEl = - 1 maxEl = - 1 ; while ( true ) { Node curr = pq . poll (); int minVal = curr . val ; // Update range if better if ( maxVal - minVal < minRange ) { minRange = maxVal - minVal ; minEl = minVal ; maxEl = maxVal ; } // If we've reached the end of a list break if ( curr . col + 1 == n ) break ; // Push next element from the same list int nextVal = arr [ curr . row ][ curr . col + 1 ] ; pq . add ( new Node ( nextVal curr . row curr . col + 1 )); maxVal = Math . max ( maxVal nextVal ); } // Return result as ArrayList ArrayList < Integer > result = new ArrayList <> (); result . add ( minEl ); result . add ( maxEl ); return result ; } // 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 } }; ArrayList < Integer > res = findSmallestRange ( arr ); System . out . println ( res . get ( 0 ) + ' ' + res . get ( 1 )); } }
C# import heapq # Function to find the smallest range def findSmallestRange ( arr ): k = len ( arr ) n = len ( arr [ 0 ]) heap = [] maxVal = float ( '-inf' ) # Push the first element of each # list into the min-heap for i in range ( k ): heapq . heappush ( heap ( arr [ i ][ 0 ] i 0 )) maxVal = max ( maxVal arr [ i ][ 0 ]) minRange = float ( 'inf' ) minEl = maxEl = - 1 while True : minVal row col = heapq . heappop ( heap ) # Update range if better if maxVal - minVal < minRange : minRange = maxVal - minVal minEl = minVal maxEl = maxVal # If we've reached the end of a list break if col + 1 == n : break # Push next element from the same list nextVal = arr [ row ][ col + 1 ] heapq . heappush ( heap ( nextVal row col + 1 )) maxVal = max ( maxVal nextVal ) return [ minEl maxEl ] # Driver code if __name__ == '__main__' : arr = [ [ 4 7 9 12 15 ] [ 0 8 10 14 20 ] [ 6 12 16 30 50 ] ] res = findSmallestRange ( arr ) print ( res [ 0 ] res [ 1 ])
JavaScript using System ; using System.Collections.Generic ; // Class to represent elements in the heap class Node : IComparable < Node > { public int val row col ; public Node ( int val int row int col ) { this . val = val ; this . row = row ; this . col = col ; } // For min-heap based on value public int CompareTo ( Node other ) { if ( this . val != other . val ) return this . val . CompareTo ( other . val ); // To avoid duplicate keys in SortedSet if ( this . row != other . row ) return this . row . CompareTo ( other . row ); return this . col . CompareTo ( other . col ); } } class GfG { // Function to find the smallest range static List < int > findSmallestRange ( int [] arr ) { int k = arr . GetLength ( 0 ); int n = arr . GetLength ( 1 ); var pq = new SortedSet < Node > (); int maxVal = int . MinValue ; // Push the first element of each list into the min-heap for ( int i = 0 ; i < k ; i ++ ) { var node = new Node ( arr [ i 0 ] i 0 ); pq . Add ( node ); maxVal = Math . Max ( maxVal arr [ i 0 ]); } int minRange = int . MaxValue minEl = - 1 maxEl = - 1 ; while ( true ) { var curr = GetMin ( pq ); pq . Remove ( curr ); int minVal = curr . val ; // Update range if better if ( maxVal - minVal < minRange ) { minRange = maxVal - minVal ; minEl = minVal ; maxEl = maxVal ; } // If we've reached the end of a list break if ( curr . col + 1 == n ) break ; // Push next element from the same list int nextVal = arr [ curr . row curr . col + 1 ]; var nextNode = new Node ( nextVal curr . row curr . col + 1 ); pq . Add ( nextNode ); maxVal = Math . Max ( maxVal nextVal ); } return new List < int > { minEl maxEl }; // Return result as List
class Node { constructor ( val row col ) { this . val = val ; this . row = row ; this . col = col ; } } // Function to find the smallest range function findSmallestRange ( arr ) { const k = arr . length ; const n = arr [ 0 ]. length ; const heap = new MinHeap (); let maxVal = - Infinity ; // Push the first element of each list into the min-heap for ( let i = 0 ; i < k ; i ++ ) { heap . push ( new Node ( arr [ i ][ 0 ] i 0 )); maxVal = Math . max ( maxVal arr [ i ][ 0 ]); } let minRange = Infinity ; let minEl = - 1 maxEl = - 1 ; while ( true ) { const curr = heap . pop (); const minVal = curr . val ; // Update range if better if ( maxVal - minVal < minRange ) { minRange = maxVal - minVal ; minEl = minVal ; maxEl = maxVal ; } // If we've reached the end of a list break if ( curr . col + 1 === n ) break ; // Push next element from the same list const nextVal = arr [ curr . row ][ curr . col + 1 ]; heap . push ( new Node ( nextVal curr . row curr . col + 1 )); maxVal = Math . max ( maxVal nextVal ); } return [ minEl maxEl ]; } // Min-heap comparator class MinHeap { constructor () { this . heap = []; } push ( node ) { this . heap . push ( node ); this . _heapifyUp (); } pop () { if ( this . size () === 1 ) return this . heap . pop (); const top = this . heap [ 0 ]; this . heap [ 0 ] = this . heap . pop (); this . _heapifyDown (); return top ; } top () { return this . heap [ 0 ]; } size () { return this . heap . length ; } _heapifyUp () { let idx = this . size () - 1 ; while ( idx > 0 ) { let parent = Math . floor (( idx - 1 ) / 2 ); if ( this . heap [ parent ]. val <= this . heap [ idx ]. val ) break ; [ this . heap [ parent ] this . heap [ idx ]] = [ this . heap [ idx ] this . heap [ parent ]]; idx = parent ; } } _heapifyDown () { let idx = 0 ; const n = this . size (); while ( true ) { let left = 2 * idx + 1 ; let right = 2 * idx + 2 ; let smallest = idx ; if ( left < n && this . heap [ left ]. val < this . heap [ smallest ]. val ) { smallest = left ; } if ( right < n && this . heap [ right ]. val < this . heap [ smallest ]. val ) { smallest = right ; } if ( smallest === idx ) break ; [ this . heap [ smallest ] this . heap [ idx ]] = [ this . heap [ idx ] this . heap [ smallest ]]; idx = smallest ; } } } // Driver code const arr = [ [ 4 7 9 12 15 ] [ 0 8 10 14 20 ] [ 6 12 16 30 50 ] ]; const res = findSmallestRange ( arr ); console . log ( res [ 0 ] + ' ' + res [ 1 ]);
Saída
6 8
