Dada una array de tamaño n*n, la tarea es imprimir sus elementos en un patrón diagonal.
Input : mat[3][3] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}}
Output : 1 2 4 7 5 3 6 8 9.
Explanation: Start from 1
Then from upward to downward diagonally i.e. 2 and 4
Then from downward to upward diagonally i.e 7, 5, 3
Then from up to down diagonally i.e 6, 8
Then down to up i.e. end at 9.
Input : mat[4][4] = {{1, 2, 3, 10},
{4, 5, 6, 11},
{7, 8, 9, 12},
{13, 14, 15, 16}}
Output: 1 2 4 7 5 3 10 6 8 13 14 9 11 12 15 16 .
Explanation: Start from 1
Then from upward to downward diagonally i.e. 2 and 4
Then from downward to upward diagonally i.e 7, 5, 3
Then from upward to downward diagonally i.e. 10 6 8 13
Then from downward to upward diagonally i.e 14 9 11
Then from upward to downward diagonally i.e. 12 15
then end at 16
Enfoque: Del diagrama se puede ver que cada elemento está impreso en diagonal hacia arriba o en diagonal hacia abajo. Comience desde el índice (0,0) e imprima los elementos en diagonal hacia arriba, luego cambie la dirección, cambie la columna e imprima en diagonal hacia abajo. Este ciclo continúa hasta que se alcanza el último elemento.
Algoritmo:
- Cree variables i=0, j=0 para almacenar los índices actuales de fila y columna
- Ejecute un ciclo de 0 a n*n, donde n es el lado de la array.
- Use una bandera isUp para decidir si la dirección es hacia arriba o hacia abajo. Establezca isUp = true inicialmente, la dirección va hacia arriba.
- Si isUp = 1, comience a imprimir elementos aumentando el índice de columna y disminuyendo el índice de fila.
- De manera similar, si isUp = 0, disminuya el índice de la columna e incremente el índice de la fila.
- Mover a la siguiente columna o fila (siguiente fila y columna de inicio
- Haga esto hasta que todos los elementos sean atravesados.
Implementación:
C++
// C++ program to print matrix in diagonal order
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
void printMatrixDiagonal(int mat[MAX][MAX], int n)
{
// Initialize indexes of element to be printed next
int i = 0, j = 0;
// Direction is initially from down to up
bool isUp = true;
// Traverse the matrix till all elements get traversed
for (int k = 0; k < n * n;) {
// If isUp = true then traverse from downward
// to upward
if (isUp) {
for (; i >= 0 && j < n; j++, i--) {
cout << mat[i][j] << " ";
k++;
}
// Set i and j according to direction
if (i < 0 && j <= n - 1)
i = 0;
if (j == n)
i = i + 2, j--;
}
// If isUp = 0 then traverse up to down
else {
for (; j >= 0 && i < n; i++, j--) {
cout << mat[i][j] << " ";
k++;
}
// Set i and j according to direction
if (j < 0 && i <= n - 1)
j = 0;
if (i == n)
j = j + 2, i--;
}
// Revert the isUp to change the direction
isUp = !isUp;
}
}
int main()
{
int mat[MAX][MAX] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
int n = 3;
printMatrixDiagonal(mat, n);
return 0;
}
Java
// Java program to print matrix in diagonal order
class GFG {
static final int MAX = 100;
static void printMatrixDiagonal(int mat[][], int n)
{
// Initialize indexes of element to be printed next
int i = 0, j = 0;
// Direction is initially from down to up
boolean isUp = true;
// Traverse the matrix till all elements get traversed
for (int k = 0; k < n * n;) {
// If isUp = true then traverse from downward
// to upward
if (isUp) {
for (; i >= 0 && j < n; j++, i--) {
System.out.print(mat[i][j] + " ");
k++;
}
// Set i and j according to direction
if (i < 0 && j <= n - 1)
i = 0;
if (j == n) {
i = i + 2;
j--;
}
}
// If isUp = 0 then traverse up to down
else {
for (; j >= 0 && i < n; i++, j--) {
System.out.print(mat[i][j] + " ");
k++;
}
// Set i and j according to direction
if (j < 0 && i <= n - 1)
j = 0;
if (i == n) {
j = j + 2;
i--;
}
}
// Revert the isUp to change the direction
isUp = !isUp;
}
}
// Driver code
public static void main(String[] args)
{
int mat[][] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
int n = 3;
printMatrixDiagonal(mat, n);
}
}
// This code is contributed by Anant Agarwal.
Python 3
# Python 3 program to print matrix in diagonal order MAX = 100 def printMatrixDiagonal(mat, n): # Initialize indexes of element to be printed next i = 0 j = 0 k = 0 # Direction is initially from down to up isUp = True # Traverse the matrix till all elements get traversed while k<n * n: # If isUp = True then traverse from downward # to upward if isUp: while i >= 0 and j<n : print(str(mat[i][j]), end = " ") k += 1 j += 1 i -= 1 # Set i and j according to direction if i < 0 and j <= n - 1: i = 0 if j == n: i = i + 2 j -= 1 # If isUp = 0 then traverse up to down else: while j >= 0 and i<n : print(mat[i][j], end = " ") k += 1 i += 1 j -= 1 # Set i and j according to direction if j < 0 and i <= n - 1: j = 0 if i == n: j = j + 2 i -= 1 # Revert the isUp to change the direction isUp = not isUp # Driver program if __name__ == "__main__": mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9] ] n = 3 printMatrixDiagonal(mat, n) # This code is contributed by Chitra Nayal
C#
// C# program to print matrix in diagonal order
using System;
class GFG {
static int MAX = 100;
static void printMatrixDiagonal(int[, ] mat, int n)
{
// Initialize indexes of element to be printed next
int i = 0, j = 0;
// Direction is initially from down to up
bool isUp = true;
// Traverse the matrix till all elements get traversed
for (int k = 0; k < n * n;) {
// If isUp = true then traverse from downward
// to upward
if (isUp) {
for (; i >= 0 && j < n; j++, i--) {
Console.Write(mat[i, j] + " ");
k++;
}
// Set i and j according to direction
if (i < 0 && j <= n - 1)
i = 0;
if (j == n) {
i = i + 2;
j--;
}
}
// If isUp = 0 then traverse up to down
else {
for (; j >= 0 && i < n; i++, j--) {
Console.Write(mat[i, j] + " ");
k++;
}
// Set i and j according to direction
if (j < 0 && i <= n - 1)
j = 0;
if (i == n) {
j = j + 2;
i--;
}
}
// Revert the isUp to change the direction
isUp = !isUp;
}
}
// Driver code
public static void Main()
{
int[, ] mat = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
int n = 3;
printMatrixDiagonal(mat, n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// php program to print matrix
// in diagonal order
$MAX = 100;
function printMatrixDiagonal($mat, $n)
{
// Initialize indexes of element
// to be printed next
$i = 0;
$j = 0 ;
// Direction is initially
// from down to up
$isUp = true;
// Traverse the matrix till
// all elements get traversed
for ($k = 0;$k < $n * $n😉
{
// If isUp = true then traverse
// from downward to upward
if ($isUp)
{
for ( ;$i >= 0 && $j < $n;$j++, $i--)
{
echo $mat[$i][$j]." ";
$k++;
}
// Set i and j according
// to direction
if ($i < 0 && $j <= $n - 1)
$i = 0;
if ($j == $n)
{
$i = $i + 2;
$j--;
}
}
// If isUp = 0 then
// traverse up to down
else
{
for ( ; $j >= 0 &&
$i<$n ; $i++, $j--)
{
echo $mat[$i][$j]." ";
$k++;
}
// Set i and j according
// to direction
if ($j < 0 && $i <= $n - 1)
$j = 0;
if ($i == $n)
{
$j = $j + 2;
$i--;
}
}
// Revert the isUp to
// change the direction
$isUp = !$isUp;
}
}
// Driver code
$mat= array(array(1, 2, 3),
array(4, 5, 6),
array(7, 8, 9));
$n = 3;
printMatrixDiagonal($mat, $n);
// This code is contributed by Surbhi Tyagi
?>
Javascript
<script>
// Javascript program to print
// matrix in diagonal order
function printMatrixDiagonal(arr, len) {
// Initialize indices to traverse
// through the array
let i = 0, j = 0;
// Direction is initially from
// down to up
let isUp = true;
// Traverse the matrix till all
// elements get traversed
for (let k = 0; k < len * len;) {
// If isUp = true traverse from
// bottom to top
if (isUp) {
for (;i >= 0 && j < len; i--, j++) {
document.write(arr[i][j] + ' ');
k++;
}
// Set i and j according to direction
if (i < 0 && j < len) i = 0;
if (j === len) i = i + 2, j--;
}
// If isUp = false then traverse
// from top to bottom
else {
for (;j >= 0 && i < len; i++, j--) {
document.write(arr[i][j] + ' ');
k++;
}
// Set i and j according to direction
if (j < 0 && i < len) j = 0;
if (i === len) j = j + 2, i--;
}
// Inverse the value of isUp to
// change the direction
isUp = !isUp
}
}
// function call
let arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
let arrLength = arr.length;
printMatrixDiagonal(arr, arrLength);
// This code is contributed by karthiksrinivasprasad
</script>
Producción:
1 2 4 7 5 3 6 8 9
Análisis de Complejidad:
- Complejidad temporal: O(n*n).
Para atravesar la array O(n*n) se necesita complejidad temporal. - Espacio Auxiliar: O(1).
Como no se requiere espacio adicional.
Implementación alternativa: esta es otra implementación simple y compacta del mismo enfoque mencionado anteriormente.
C++
// C++ program to print matrix in diagonal order
#include <bits/stdc++.h>
using namespace std;
int main()
{
// Initialize matrix
int mat[][4] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// n - size
// mode - switch to derive up/down traversal
// it - iterator count - increases until it
// reaches n and then decreases
int n = 4, mode = 0, it = 0, lower = 0;
// 2n will be the number of iterations
for (int t = 0; t < (2 * n - 1); t++) {
int t1 = t;
if (t1 >= n) {
mode++;
t1 = n - 1;
it--;
lower++;
}
else {
lower = 0;
it++;
}
for (int i = t1; i >= lower; i--) {
if ((t1 + mode) % 2 == 0) {
cout << (mat[i][t1 + lower - i]) << endl;
}
else {
cout << (mat[t1 + lower - i][i]) << endl;
}
}
}
return 0;
}
// This code is contributed by princiraj1992
Java
// Java program to print matrix in diagonal order
public class MatrixDiag {
public static void main(String[] args)
{
// Initialize matrix
int[][] mat = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// n - size
// mode - switch to derive up/down traversal
// it - iterator count - increases until it
// reaches n and then decreases
int n = 4, mode = 0, it = 0, lower = 0;
// 2n will be the number of iterations
for (int t = 0; t < (2 * n - 1); t++) {
int t1 = t;
if (t1 >= n) {
mode++;
t1 = n - 1;
it--;
lower++;
}
else {
lower = 0;
it++;
}
for (int i = t1; i >= lower; i--) {
if ((t1 + mode) % 2 == 0) {
System.out.println(mat[i][t1 + lower - i]);
}
else {
System.out.println(mat[t1 + lower - i][i]);
}
}
}
}
}
Python3
# Python3 program to print matrix in diagonal order # Driver code # Initialize matrix mat = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ]]; # n - size # mode - switch to derive up/down traversal # it - iterator count - increases until it # reaches n and then decreases n = 4 mode = 0 it = 0 lower = 0 # 2n will be the number of iterations for t in range(2 * n - 1): t1 = t if (t1 >= n): mode += 1 t1 = n - 1 it -= 1 lower += 1 else: lower = 0 it += 1 for i in range(t1, lower - 1, -1): if ((t1 + mode) % 2 == 0): print((mat[i][t1 + lower - i])) else: print(mat[t1 + lower - i][i]) # This code is contributed by princiraj1992
C#
// C# program to print matrix in diagonal order
using System;
public class MatrixDiag {
// Driver code
public static void Main(String[] args)
{
// Initialize matrix
int[, ] mat = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// n - size
// mode - switch to derive up/down traversal
// it - iterator count - increases until it
// reaches n and then decreases
int n = 4, mode = 0, it = 0, lower = 0;
// 2n will be the number of iterations
for (int t = 0; t < (2 * n - 1); t++) {
int t1 = t;
if (t1 >= n) {
mode++;
t1 = n - 1;
it--;
lower++;
}
else {
lower = 0;
it++;
}
for (int i = t1; i >= lower; i--) {
if ((t1 + mode) % 2 == 0) {
Console.WriteLine(mat[i, t1 + lower - i]);
}
else {
Console.WriteLine(mat[t1 + lower - i, i]);
}
}
}
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to print an n * n matrix in diagonal order
function MatrixDiag(arr){
// n - size of the array
// mode - to switch from top/bottom traversal
// it - iterator count - increases until it
// reaches n and then decreases
// lower - to ensure we move to the
// next row when columns go out of bounds
let n = arr.length, mode = 0, it = 0, lower = 0;
// A 4 * 4 matrix has 7 diagonals.
// Hence (2 * n -1) iterations
for(let t=0; t< (2 * n - 1); t++){
let t1 = t;
if(t1 >= n){
mode++;
t1 = n - 1;
it--;
lower++;
} else {
lower = 0;
it++;
}
for(let i = t1; i>= lower; i--){
if((t1 + mode) % 2 === 0){
console.log(arr[i][t1 + lower - i])
} else{
console.log(arr[t1 + lower - i][i])
}
}
}
}
// function call
let arr = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
];
MatrixDiag(arr)
// This code is contributed by karthiksrinivasprasad
</script>
Producción:
1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16
Complejidad temporal: O(n 2 ).
Espacio Auxiliar: O(1).
Este artículo es una contribución de Aarti_Rathi y Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo 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