Dado un vector 2D de números enteros NxM. La tarea es ordenar los elementos de los vectores en diagonal de arriba a la izquierda a abajo a la derecha en orden decreciente.
Ejemplos:
Entrada: arr[][] = { { 10, 2, 3 }, { 4, 5, 6 }, {7, 8, 9 } }
Salida:
10 6 3
8 9 2
7 4 5
Entrada: arr[][ ] = { { 10, 2, 43 }, { 40, 5, 16 }, { 71, 8, 29 }, {1, 100, 5} }
Salida:
29 16 43
40 10 2
100 8 5
1 71 5
Enfoque:
Observaciones:
Las imágenes de arriba muestran la diferencia entre el índice de columna y el índice de fila en cada celda. Las celdas que tienen la misma diferencia entre la celda de arriba a la izquierda y la de abajo hacia abajo forman una diagonal.
A continuación se muestran los pasos para ordenar la diagonal en orden decreciente:
- Almacene el elemento diagonal con una diferencia positiva en una array de vectores (por ejemplo , Pos[] ) de modo que los elementos en la celda que tienen una diferencia (por ejemplo , a ) se almacenen en el índice an de la array Pos[] .
- Almacene el elemento diagonal con la diferencia negativa en otra array de vectores (digamos Neg[] ) de modo que los elementos en la celda que tienen diferencia (digamos -b ) se almacenen en el índice abs(-b) = b de la array Neg[] .
- Ordene tanto la array de vectores en orden creciente.
- Recorra el vector 2D dado y actualice el valor en la celda actual con el valor almacenado en la array Pos[] y Neg[].
- Si la diferencia entre el índice de columna y fila (por ejemplo, d ) es positiva, actualice el valor de la array Pos[d] y elimine el último elemento como:
- Si la diferencia entre el índice de columna y fila (por ejemplo, d ) es positiva, actualice el valor de la array Pos[d] y elimine el último elemento como:
d = i - j arr[i][j] = Pos[d][Pos.size()-1] Pos[d].pop_back()
- Si la diferencia entre el índice de columna y fila (por ejemplo, d ) es negativa, actualice el valor de la array Neg[d] y elimine el último elemento como:
d = j - i arr[i][j] = Neg[d][Neg.size()-1] Neg[d].pop_back()
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to sort the 2D vector
// diagonally in decreasing order
#include "bits/stdc++.h"
using namespace std;
// Function that sort the elements
// of 2D vector
void diagonalSort(vector<vector<int> >& mat)
{
// Calculate the rows and column
int row = mat.size();
int col = mat[0].size();
// Array of vectors to store the
// diagonal elements
vector<int> Neg[row];
vector<int> Pos[col];
// Traverse the 2D vector and put
// element in Array of vectors at
// index difference between indexes
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
// If diff is negative, then
// push element to Neg[]
if (j < i) {
Neg[i - j].push_back(mat[i][j]);
}
// If diff is positive, then
// push element to Pos[]
else if (j > i) {
Pos[j - i].push_back(mat[i][j]);
}
// If diff is 0, then push
// element to Pos[0]
else {
Pos[0].push_back(mat[i][j]);
}
}
}
// Sort the Array of vectors
for (int i = 0; i < row; i++) {
sort(Neg[i].begin(), Neg[i].end());
}
for (int i = 0; i < col; i++) {
sort(Pos[i].begin(), Pos[i].end());
}
// Update the value to arr[][]
// from the sorted Array of vectors
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
// If diff is positive
if (j < i) {
int d = i - j;
int l = Neg[d].size();
mat[i][j] = Neg[d][l - 1];
Neg[d].pop_back();
}
// If diff is negative
else if (j > i) {
int d = j - i;
int l = Pos[d].size();
mat[i][j] = Pos[d][l - 1];
Pos[d].pop_back();
}
// If diff is 0
else {
int l = Pos[0].size();
mat[i][j] = Pos[0][l - 1];
Pos[0].pop_back();
}
}
}
}
// Function to print element
void printElement(vector<vector<int> >& arr)
{
// Traverse the 2D vector
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr[0].size(); j++) {
cout << arr[i][j] << ' ';
}
cout << endl;
}
}
// Driver Code
int main()
{
vector<vector<int> > arr
= { { 10, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
diagonalSort(arr);
// Function call to print elements
printElement(arr);
}
Java
// Java program to sort the 2D matrix
// diagonally in decreasing order
import java.io.*;
import java.util.*;
class GFG {
public static void
diagonalSort(ArrayList<ArrayList<Integer> > mat)
{
// Calculate the rows and column
int row = mat.size();
int col = mat.get(0).size();
// Arraylist of Arraylist to store the
// diagonal elements
ArrayList<ArrayList<Integer> > Neg
= new ArrayList<ArrayList<Integer> >();
ArrayList<ArrayList<Integer> > Pos
= new ArrayList<ArrayList<Integer> >();
int i, j;
for (i = 0; i < row; i++) {
ArrayList<Integer> temp
= new ArrayList<Integer>();
Neg.add(temp);
}
for (j = 0; j < col; j++) {
ArrayList<Integer> temp
= new ArrayList<Integer>();
Pos.add(temp);
}
// Traverse the 2D matrix and put
// element in Arraylist of Arraylist at
// index difference between indexes
for (i = 0; i < row; i++) {
for (j = 0; j < col; j++) {
// If diff is negative, then
// push element to Neg[]
if (j < i) {
Neg.get(i - j).add(mat.get(i).get(j));
}
// If diff is positive, then
// push element to Pos[]
else if (i < j) {
Pos.get(j - i).add(mat.get(i).get(j));
}
// If diff is 0, then push
// element to Pos[0]
else {
Pos.get(0).add(mat.get(i).get(j));
}
}
}
// Sort the Array of vectors
for (i = 0; i < row; i++) {
Collections.sort(Neg.get(i));
;
}
for (i = 0; i < col; i++) {
Collections.sort(Pos.get(i));
;
}
// Update the value to mat
// from the sorted Arraylist of Arraylist
for (i = 0; i < row; i++) {
for (j = 0; j < col; j++) {
// If diff is positive
if (j < i) {
int d = i - j;
int l = Neg.get(d).size();
mat.get(i).set(j,
Neg.get(d).get(l - 1));
Neg.get(d).remove(l - 1);
}
// If diff is negative
else if (i < j) {
int d = j - i;
int l = Pos.get(d).size();
mat.get(i).set(j,
Pos.get(d).get(l - 1));
Pos.get(d).remove(l - 1);
}
// If diff is 0
else {
int l = Pos.get(0).size();
mat.get(i).set(j,
Pos.get(0).get(l - 1));
Pos.get(0).remove(l - 1);
}
}
}
// Print diagonally sorted matrix
for (i = 0; i < row; i++) {
for (j = 0; j < col; j++) {
System.out.print(mat.get(i).get(j) + " ");
}
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
ArrayList<ArrayList<Integer> > arr
= new ArrayList<ArrayList<Integer> >();
ArrayList<Integer> row1 = new ArrayList<Integer>();
row1.add(10);
row1.add(2);
row1.add(3);
arr.add(row1);
ArrayList<Integer> row2 = new ArrayList<Integer>();
row2.add(4);
row2.add(5);
row2.add(6);
arr.add(row2);
ArrayList<Integer> row3 = new ArrayList<Integer>();
row3.add(7);
row3.add(8);
row3.add(9);
arr.add(row3);
diagonalSort(arr);
}
}
// This code is contributed by Snigdha Patil
Python3
# Python program for the above approach from collections import defaultdict def diagonalSort(matrix, n, m): # make a dict of list, where we # will store the diagonal elements to = defaultdict(list) # store the diagonal elements with # respect to their row-col value # remember every row-col value for # each diagonal will be different for row in range(n): for col in range(m): to[row-col].append(matrix[row][col]) # sort the elements of each # diagonal as required for i in to: to[i].sort(reverse=True) # store the new diagonal elements to # their respective position in the matrix for row in range(n): for col in range(m): matrix[row][col] = to[row-col].pop(0) return matrix # Driver Code if __name__ == "__main__": matrix = [[10, 2, 3], [4, 5, 6], [7, 8, 9]] n = len(matrix) m = len(matrix[0]) matrix = diagonalSort(matrix, n, m) for row in range(n): for col in range(m): print(matrix[row][col], end=' ') print() # This code is contributed by ajaymakvana.
Producción
10 6 3 8 9 2 7 4 5
Complejidad de tiempo: O(N*M*log(min(N,M)))
Complejidad espacial : O(N*M)
Método 2:
aquí en este método, haremos la optimización del espacio en el método anterior. aquí atravesamos la array diagonal y almacenamos sus valores en la array 1D adicional, por lo que para cada diagonal necesitaremos almacenar el elemento mínimo mínimo (n, m) en nuestra array 1D, por lo que esta es la optimización del espacio en la solución anterior
C++
// C++ program to sort the 2D vector
// diagonally in decreasing order
#include <bits/stdc++.h>
using namespace std;
// Function that sort 2D matrix Diagonally In Descending order
void diagonalSort(vector<vector<int> >& mat)
{
// Calculate the rows and column
int n = mat.size();
int m = mat[0].size();
// 1D array for extra space
vector<int> v;
// start traversing from first row to nth row
// where first row to nth row is first member of diagonal
for (int row = 0; row < n; row++) {
// take all diagonal element where first element is
// mat[row][0] means left column of matrix
for (int j = 0, i = row; i < n && j < m; i++, j++) {
v.push_back(mat[i][j]);
}
// sort element in reverse order because we need
// decreasing order in diagonal
sort(v.rbegin(), v.rend());
int t = 0;
// putting this all values to matrix in descending sorted order
for (int j = 0, i = row; i < n && j < m; i++, j++) {
mat[i][j] = v[t++];
}
v.clear();
}
// start traversing from second column to mth column
// where second column to mth column is first member of diagonal
// note that here we can't start from first column
// because it is already sorted by first row processing
for (int col = 1; col < m; col++) {
// take all diagonal element where first element is
// mat[0][col] means first row of matrix
for (int j = col, i = 0; i < n && j < m; i++, j++) {
v.push_back(mat[i][j]);
}
// sort element in reverse order because we need
// decreasing order in diagonal
sort(v.rbegin(), v.rend());
int t = 0;
// putting this all values to matrix in descending sorted order
for (int j = col, i = 0; i < n && j < m; i++, j++) {
mat[i][j] = v[t++];
}
v.clear();
}
}
// Function to print element
void printElement(vector<vector<int> >& arr)
{
// Traverse the 2D vector
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr[0].size(); j++) {
cout << arr[i][j] << ' ';
}
cout << endl;
}
}
// Driver Code
int main()
{
vector<vector<int> > arr = {{ 10, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
diagonalSort(arr);
// Function call to print elements
printElement(arr);
}
Java
// Java program to sort the 2D matrix
// diagonally in decreasing order
import java.io.*;
import java.util.*;
class GFG
{
// Function that sort 2D matrix Diagonally In Descending
// order
public static void
diagonalSort(ArrayList<ArrayList<Integer> > mat)
{
// Calculate the rows and column
int n = mat.size();
int m = mat.get(0).size();
// 1D array for extra space
ArrayList<Integer> v = new ArrayList<Integer>();
// start traversing from first row to nth row
// where first row to nth row is first member of
// diagonal
for (int row = 0; row < n; row++)
{
// take all diagonal element where first element
// is mat[row][0] means left column of matrix
for (int j = 0, i = row; j < m && i < n;
i++, j++) {
v.add(mat.get(i).get(j));
}
// sort element in reverse order because we need
// decreasing order in diagonal
Collections.sort(v, Collections.reverseOrder());
int t = 0;
for (int j = 0, i = row; j < m && i < n;
i++, j++) {
mat.get(i).set(j, v.get(t++));
}
v.clear();
}
// start traversing from second column to mth column
// where second column to mth column is first member
// of diagonal note that here we can't start from
// first column because it is already sorted by
// first row processing
for (int col = 1; col < m; col++)
{
// take all diagonal element where first element
// is mat[0][col] means first row of matrix
for (int j = col, i = 0; i < n && j < m;
i++, j++) {
v.add(mat.get(i).get(j));
}
// sort element in reverse order because we need
// decreasing order in diagonal
Collections.sort(v, Collections.reverseOrder());
int t = 0;
// putting this all values to matrix in
// descending sorted order
for (int j = col, i = 0; i < n && j < m;
i++, j++) {
mat.get(i).set(j, v.get(t++));
}
v.clear();
}
// Print diagonally sorted matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(mat.get(i).get(j) + " ");
}
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
ArrayList<ArrayList<Integer> > arr
= new ArrayList<ArrayList<Integer> >();
ArrayList<Integer> row1 = new ArrayList<Integer>();
row1.add(10);
row1.add(2);
row1.add(3);
arr.add(row1);
ArrayList<Integer> row2 = new ArrayList<Integer>();
row2.add(4);
row2.add(5);
row2.add(6);
arr.add(row2);
ArrayList<Integer> row3 = new ArrayList<Integer>();
row3.add(7);
row3.add(8);
row3.add(9);
arr.add(row3);
diagonalSort(arr);
}
}
// This code is contributed by Snigdha Patil
Python3
# Python program to sort the 2D vector diagonally in decreasing order # Function that sort 2D matrix Diagonally In Descending order def DiagonalSort(mat): # Calculate the rows and column n = len(mat) m = len(mat[0]) # 1D array for extra space v = [] # start traversing from first row to nth row # where first row to nth row is first member of diagonal for row in range(0, n): j = 0 i = row # take all diagonal element where first element is # mat[row][0] means left column of matrix while(i < n and j < m): v.append(mat[i][j]) i += 1 j += 1 # sort element in reverse order because we need # decreasing order in diagonal v.sort(reverse=True) v[::-1] t = 0 j = 0 i = row # putting this all values to matrix in descending sorted order while(i < n and j < m): mat[i][j] = v[t] t += 1 i += 1 j += 1 v = [] # start traversing from second column to mth column # where second column to mth column is first member of diagonal # note that here we can't start from first column # because it is already sorted by first row processing for col in range(0, m): j = col i = 0 # take all diagonal element where first element is # mat[0][col] means first row of matrix while(i < n and j < m): v.append(mat[i][j]) i += 1 j += 1 # sort element in reverse order because we need # decreasing order in diagonal v.sort(reverse=True) v[::-1] t = 0 j = col i = 0 # putting this all values to matrix in descending sorted order while(i < n and j < m): mat[i][j] = v[t] t += 1 i += 1 j += 1 v = [] return mat # Function to print element def printElement(arr): n = len(arr) m = len(arr[0]) # Traverse the 2D array for i in range(0, n): for j in range(0, m): print(arr[i][j], end=" ") print() # Driver Code arr = [[10, 2, 3], [4, 5, 6], [7, 8, 9]] DiagonalSort(arr) printElement(arr)
Producción
10 6 3 8 9 2 7 4 5
Complejidad de tiempo: O(N*M*log(min(N,M)))
Espacio auxiliar: O(min(N,M))
Publicación traducida automáticamente
Artículo escrito por prateek2006 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA