Dada una array nxn, donde cada fila y columna se ordena en orden no decreciente. Imprime todos los elementos de la array en orden ordenado.
Ejemplo:
Entrada: mat[][] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50},
} ;
Salida: 10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
Podemos usar Young Tableau para resolver el problema anterior. La idea es considerar la array 2D dada como Young Tableau y llamar al extracto mínimo O (N)
C++
// A C++ program to Print all elements in sorted order from row and
// column wise sorted matrix
#include<iostream>
#include<climits>
using namespace std;
#define INF INT_MAX
#define N 4
// A utility function to youngify a Young Tableau. This is different
// from standard youngify. It assumes that the value at mat[0][0] is
// infinite.
void youngify(int mat[][N], int i, int j)
{
// Find the values at down and right sides of mat[i][j]
int downVal = (i+1 < N)? mat[i+1][j]: INF;
int rightVal = (j+1 < N)? mat[i][j+1]: INF;
// If mat[i][j] is the down right corner element, return
if (downVal==INF && rightVal==INF)
return;
// Move the smaller of two values (downVal and rightVal) to
// mat[i][j] and recur for smaller value
if (downVal < rightVal)
{
mat[i][j] = downVal;
mat[i+1][j] = INF;
youngify(mat, i+1, j);
}
else
{
mat[i][j] = rightVal;
mat[i][j+1] = INF;
youngify(mat, i, j+1);
}
}
// A utility function to extract minimum element from Young tableau
int extractMin(int mat[][N])
{
int ret = mat[0][0];
mat[0][0] = INF;
youngify(mat, 0, 0);
return ret;
}
// This function uses extractMin() to print elements in sorted order
void printSorted(int mat[][N])
{
for (int i=0; i<N*N; i++)
cout << extractMin(mat) << " ";
}
// driver program to test above function
int main()
{
int mat[N][N] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50},
};
printSorted(mat);
return 0;
}
Java
// A Java program to Print all elements
// in sorted order from row and
// column wise sorted matrix
class GFG
{
static final int INF = Integer.MAX_VALUE;
static final int N = 4;
// A utility function to youngify a Young Tableau.
// This is different from standard youngify.
// It assumes that the value at mat[0][0] is infinite.
static void youngify(int mat[][], int i, int j)
{
// Find the values at down and right sides of mat[i][j]
int downVal = (i + 1 < N) ?
mat[i + 1][j] : INF;
int rightVal = (j + 1 < N) ?
mat[i][j + 1] : INF;
// If mat[i][j] is the down right corner element,
// return
if (downVal == INF && rightVal == INF)
{
return;
}
// Move the smaller of two values
// (downVal and rightVal) to mat[i][j]
// and recur for smaller value
if (downVal < rightVal)
{
mat[i][j] = downVal;
mat[i + 1][j] = INF;
youngify(mat, i + 1, j);
}
else
{
mat[i][j] = rightVal;
mat[i][j + 1] = INF;
youngify(mat, i, j + 1);
}
}
// A utility function to extract
// minimum element from Young tableau
static int extractMin(int mat[][])
{
int ret = mat[0][0];
mat[0][0] = INF;
youngify(mat, 0, 0);
return ret;
}
// This function uses extractMin()
// to print elements in sorted order
static void printSorted(int mat[][])
{
System.out.println("Elements of matrix in sorted order n");
for (int i = 0; i < N * N; i++)
{
System.out.print(extractMin(mat) + " ");
}
}
// Driver Code
public static void main(String args[])
{
int mat[][] = {{10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
printSorted(mat);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 program to Print all elements
# in sorted order from row and column
# wise sorted matrix
import sys
INF = sys.maxsize
N = 4
# A utility function to youngify a Young
# Tableau. This is different from standard
# youngify. It assumes that the value at
# mat[0][0] is infinite.
def youngify(mat, i, j):
# Find the values at down and
# right sides of mat[i][j]
downVal = mat[i + 1][j] if (i + 1 < N) else INF
rightVal = mat[i][j + 1] if (j + 1 < N) else INF
# If mat[i][j] is the down right
# corner element, return
if (downVal == INF and rightVal == INF):
return
# Move the smaller of two values
# (downVal and rightVal) to mat[i][j]
# and recur for smaller value
if (downVal < rightVal):
mat[i][j] = downVal
mat[i + 1][j] = INF
youngify(mat, i + 1, j)
else:
mat[i][j] = rightVal
mat[i][j + 1] = INF
youngify(mat, i, j + 1)
# A utility function to extract minimum
# element from Young tableau
def extractMin(mat):
ret = mat[0][0]
mat[0][0] = INF
youngify(mat, 0, 0)
return ret
# This function uses extractMin() to
# print elements in sorted order
def printSorted(mat):
print("Elements of matrix in sorted order n")
i = 0
while i < N * N:
print(extractMin(mat), end = " ")
i += 1
# Driver Code
if __name__ == "__main__":
mat = [[10, 20, 30, 40],
[15, 25, 35, 45],
[27, 29, 37, 48],
[32, 33, 39, 50]]
printSorted(mat)
# This code is contributed by ita_c
C#
// A C# program to Print all elements
// in sorted order from row and
// column wise sorted matrix
using System;
class GFG
{
static int INF = int.MaxValue;
static int N = 4;
// A utility function to youngify a Young Tableau.
// This is different from standard youngify.
// It assumes that the value at mat[0][0] is infinite.
static void youngify(int [,]mat, int i, int j)
{
// Find the values at down and right sides of mat[i][j]
int downVal = (i + 1 < N) ?
mat[i + 1,j] : INF;
int rightVal = (j + 1 < N) ?
mat[i,j + 1] : INF;
// If mat[i][j] is the down right corner element,
// return
if (downVal == INF && rightVal == INF)
{
return;
}
// Move the smaller of two values
// (downVal and rightVal) to mat[i][j]
// and recur for smaller value
if (downVal < rightVal)
{
mat[i,j] = downVal;
mat[i + 1,j] = INF;
youngify(mat, i + 1, j);
}
else
{
mat[i, j] = rightVal;
mat[i, j + 1] = INF;
youngify(mat, i, j + 1);
}
}
// A utility function to extract
// minimum element from Young tableau
static int extractMin(int [,]mat)
{
int ret = mat[0,0];
mat[0, 0] = INF;
youngify(mat, 0, 0);
return ret;
}
// This function uses extractMin()
// to print elements in sorted order
static void printSorted(int [,]mat)
{
Console.WriteLine("Elements of matrix in sorted order n");
for (int i = 0; i < N * N; i++)
{
Console.Write(extractMin(mat) + " ");
}
}
// Driver Code
static public void Main ()
{
int [,]mat = {{10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
printSorted(mat);
}
}
// This code is contributed by ajit.
Javascript
<script>
// A Javascript program to Print all elements
// in sorted order from row and
// column wise sorted matrix
let INF = Number.MAX_VALUE;
let N = 4;
// A utility function to youngify a Young Tableau.
// This is different from standard youngify.
// It assumes that the value at mat[0][0] is infinite.
function youngify(mat,i,j)
{
// Find the values at down and right sides of mat[i][j]
let downVal = (i + 1 < N) ?
mat[i + 1][j] : INF;
let rightVal = (j + 1 < N) ?
mat[i][j + 1] : INF;
// If mat[i][j] is the down right corner element,
// return
if (downVal == INF && rightVal == INF)
{
return;
}
// Move the smaller of two values
// (downVal and rightVal) to mat[i][j]
// and recur for smaller value
if (downVal < rightVal)
{
mat[i][j] = downVal;
mat[i + 1][j] = INF;
youngify(mat, i + 1, j);
}
else
{
mat[i][j] = rightVal;
mat[i][j + 1] = INF;
youngify(mat, i, j + 1);
}
}
// A utility function to extract
// minimum element from Young tableau
function extractMin(mat)
{
let ret = mat[0][0];
mat[0][0] = INF;
youngify(mat, 0, 0);
return ret;
}
// This function uses extractMin()
// to print elements in sorted order
function printSorted(mat)
{
document.write("Elements of matrix in sorted order n<br>");
for (let i = 0; i < N * N; i++)
{
document.write(extractMin(mat) + " ");
}
}
let mat=[[10, 20, 30, 40],[15, 25, 35, 45],
[27, 29, 37, 48],[32, 33, 39, 50]];
printSorted(mat);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
La complejidad temporal del extracto mínimo es O(N) y se denomina O(N 2 ) veces. Por lo tanto, la complejidad temporal total es O(N 3 ).
Otro enfoque: la idea es mantener todos los elementos de la array en una array unidimensional y luego ordenar la array e imprimir todos los valores en ella.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to print all elements of matrix in sorted orderd
void sortedMatrix(int N, vector<vector<int> > Mat)
{
vector<int> temp;
// Store all elements of matrix into temp
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
temp.push_back(Mat[i][j]);
}
}
// Sort the temp
sort(temp.begin(), temp.end());
// Print the values of temp
for (int i = 0; i < temp.size(); i++) {
cout << temp[i] << " ";
}
}
int main()
{
int N = 4;
vector<vector<int> > Mat = {
{ 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 },
};
sortedMatrix(N, Mat);
return 0;
}
// This code is contributed by pratiknawale999
Java
// A Java program to Print all elements
// in sorted order from row and
// column wise sorted matrix
import java.io.*;
import java.util.*;
class GFG {
// Function to print all elements of matrix in sorted orderd
static void sortedMatrix(int N, int[][] mat)
{
List<Integer> temp = new ArrayList<Integer>();
// Store all elements of matrix into temp
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
temp.add(mat[i][j]);
}
}
// Sort the temp
Collections.sort(temp);
// Print the values of temp
for (int i = 0; i < temp.size(); i++) {
System.out.print(temp.get(i)+" ");
}
}
public static void main (String[] args) {
int N = 4;
int mat[][] = {{10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
sortedMatrix(N,mat);
}
}
// This code is contributed by shruti456rawal
Python3
# Function to print all elements of matrix in sorted orderd def sortedMatrix(N, Mat): temp = [] # Store all elements of matrix into temp for i in range(0, N): for j in range(0, N): temp.append(Mat[i][j]) # Sort the temp temp.sort() # Print the values of temp for i in range(len(temp)): print(temp[i], end=' ') if __name__ == "__main__": N = 4 Mat = [[10, 20, 30, 40], [15, 25, 35, 45], [27, 29, 37, 48], [32, 33, 39, 50]] sortedMatrix(N, list(Mat)) # This code is contributed by Aarti_Rathi
C#
using System;
using System.Collections.Generic;
public static class GFG {
// Function to print all elements of matrix in sorted
// orderd
static void sortedMatrix(int N, List<List<int> > Mat)
{
List<int> temp = new List<int>();
// Store all elements of matrix into temp
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
temp.Add(Mat[i][j]);
}
}
// Sort the temp
temp.Sort();
// Print the values of temp
for (int i = 0; i < temp.Count; i++) {
Console.Write(temp[i]);
Console.Write(" ");
}
}
public static void Main()
{
int N = 4;
List<List<int> > Mat = new List<List<int> >() {
new List<int>{ 10, 20, 30, 40 },
new List<int>{ 15, 25, 35, 45 },
new List<int>{ 27, 29, 37, 48 },
new List<int>
{
32, 33, 39, 50
}
};
sortedMatrix(N, new List<List<int> >(Mat));
}
// This code is contributed by Aarti_Rathi
}
Javascript
// A JavaScript program to Print all elements
// in sorted order from row and
// column wise sorted matrix
// Function to print all elements of matrix in sorted orderd
function sortedMatrix(N, mat)
{
var temp = [];
// Store all elements of matrix into temp
for (var i=0; i < N; i++)
{
for (var j=0; j < N; j++)
{
(temp.push(mat[i][j]));
}
}
// Sort the temp
temp.sort();
// Print the values of temp
for (var i =0; i < temp.length; i++)
{
console.log(temp[i] + " ");
}
}
var N = 4;
var mat = [[10, 20, 30, 40], [15, 25, 35, 45], [27, 29, 37, 48], [32, 33, 39, 50]];
sortedMatrix(N, mat);
// This code is contributed by Aarti_Rathi
Producción
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
Complejidad de Tiempo: O(N 2 log(N 2 ))
Espacio Auxiliar: O(N 2 )
Una mejor solución es utilizar el enfoque utilizado para fusionar k arrays ordenadas . La idea es usar un Min Heap de tamaño N que almacene elementos de la primera columna. Ellos extraen mínimo. En extraer mínimo, reemplace el elemento mínimo con el siguiente elemento de la fila de la que se extrae el elemento.
C++
// C++ program to merge k sorted arrays of size n each.
#include<iostream>
#include<climits>
using namespace std;
#define N 4
// A min heap node
struct MinHeapNode
{
int element; // The element to be stored
int i; // index of the row from which the element is taken
int j; // index of the next element to be picked from row
};
// Prototype of a utility function to swap two min heap nodes
void swap(MinHeapNode *x, MinHeapNode *y);
// A class for Min Heap
class MinHeap
{
MinHeapNode *harr; // pointer to array of elements in heap
int heap_size; // size of min heap
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); }
};
// This function prints elements of a given matrix in non-decreasing
// order. It assumes that ma[][] is sorted row wise sorted.
void printSorted(int mat[][N])
{
// Create a min heap with k heap nodes. Every heap node
// has first element of an array
MinHeapNode *harr = new MinHeapNode[N];
for (int i = 0; i < N; i++)
{
harr[i].element = mat[i][0]; // Store the first element
harr[i].i = i; // index of row
harr[i].j = 1; // Index of next element to be stored from row
}
MinHeap hp(harr, N); // Create the min heap
// Now one by one get the minimum element from min
// heap and replace it with next element of its array
for (int count = 0; count < N*N; count++)
{
// Get the minimum element and store it in output
MinHeapNode root = hp.getMin();
cout << root.element << " ";
// Find the next element that will replace current
// root of heap. The next element belongs to same
// array as the current root.
if (root.j < N)
{
root.element = mat[root.i][root.j];
root.j += 1;
}
// If root was the last element of its array
else root.element = INT_MAX; //INT_MAX is for infinite
// Replace root with next element of array
hp.replaceMin(root);
}
}
// FOLLOWING ARE IMPLEMENTATIONS OF STANDARD MIN HEAP METHODS
// FROM CORMEN BOOK
// 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);
}
}
// A utility function to swap two elements
void swap(MinHeapNode *x, MinHeapNode *y)
{
MinHeapNode temp = *x; *x = *y; *y = temp;
}
// driver program to test above function
int main()
{
int mat[N][N] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50},
};
printSorted(mat);
return 0;
}
Producción
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
Complejidad temporal: O(N 2 LogN).
Ejercicio:
Las soluciones anteriores funcionan para una array cuadrada. Extiende las soluciones anteriores para trabajar con una array rectangular M*N.
Este artículo es una contribución de Varun . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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