矩阵对角线的镜像
原文: https://www.geeksforgeeks.org/mirror-matrix-across-diagonal/
给定 2 阶N x N
的二维数组,请打印一个矩阵,该矩阵是对角线上给定树的镜像。 我们需要以某种方式打印结果,将对角线上方的三角形的值与其对角线下方的三角形的值交换,就像镜像交换一样。 打印以矩阵布局获得的二维数组。
示例:
Input : int mat[][] = {{1 2 4 }
{5 9 0}
{ 3 1 7}}
Output : 1 5 3
2 9 1
4 0 7
Input : mat[][] = {{1 2 3 4 }
{5 6 7 8 }
{9 10 11 12}
{13 14 15 16} }
Output : 1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16
此问题的简单解决方案占用了额外的空间,我们一对一地遍历所有对角线(从右到左)。 在对角线遍历期间,首先将所有元素推入栈,然后再次遍历,然后将对角线的每个元素替换为栈元素。
以下是上述想法的实现。
C++
// Simple CPP program to find mirror of
// matrix across diagonal.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
void imageSwap(int mat[][MAX], int n)
{
// for diagonal which start from at
// first row of matrix
int row = 0;
// traverse all top right diagonal
for (int j = 0; j < n; j++) {
// here we use stack for reversing
// the element of diagonal
stack<int> s;
int i = row, k = j;
while (i < n && k >= 0)
s.push(mat[i++][k--]);
// push all element back to matrix
// in reverse order
i = row, k = j;
while (i < n && k >= 0) {
mat[i++][k--] = s.top();
s.pop();
}
}
// do the same process for all the
// diagonal which start from last
// column
int column = n - 1;
for (int j = 1; j < n; j++) {
// here we use stack for reversing
// the elements of diagonal
stack<int> s;
int i = j, k = column;
while (i < n && k >= 0)
s.push(mat[i++][k--]);
// push all element back to matrix
// in reverse order
i = j;
k = column;
while (i < n && k >= 0) {
mat[i++][k--] = s.top();
s.pop();
}
}
}
// Utility function to print a matrix
void printMatrix(int mat[][MAX], int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << mat[i][j] << " ";
cout << endl;
}
}
// driver program to test above function
int main()
{
int mat[][MAX] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int n = 4;
imageSwap(mat, n);
printMatrix(mat, n);
return 0;
}
Java
// Simple Java program to find mirror of
// matrix across diagonal.
import java.util.*;
class GFG
{
static int MAX = 100;
static void imageSwap(int mat[][], int n)
{
// for diagonal which start from at
// first row of matrix
int row = 0;
// traverse all top right diagonal
for (int j = 0; j < n; j++)
{
// here we use stack for reversing
// the element of diagonal
Stack<Integer> s = new Stack<>();
int i = row, k = j;
while (i < n && k >= 0)
{
s.push(mat[i++][k--]);
}
// push all element back to matrix
// in reverse order
i = row;
k = j;
while (i < n && k >= 0)
{
mat[i++][k--] = s.peek();
s.pop();
}
}
// do the same process for all the
// diagonal which start from last
// column
int column = n - 1;
for (int j = 1; j < n; j++)
{
// here we use stack for reversing
// the elements of diagonal
Stack<Integer> s = new Stack<>();
int i = j, k = column;
while (i < n && k >= 0)
{
s.push(mat[i++][k--]);
}
// push all element back to matrix
// in reverse order
i = j;
k = column;
while (i < n && k >= 0)
{
mat[i++][k--] = s.peek();
s.pop();
}
}
}
// Utility function to print a matrix
static void printMatrix(int mat[][], int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
System.out.print(mat[i][j] + " ");
}
System.out.println("");
}
}
// Driver program to test above function
public static void main(String[] args)
{
int mat[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
int n = 4;
imageSwap(mat, n);
printMatrix(mat, n);
}
}
// This code contributed by Rajput-Ji
Python3
# Simple Python3 program to find mirror of
# matrix across diagonal.
MAX = 100
def imageSwap(mat, n):
# for diagonal which start from at
# first row of matrix
row = 0
# traverse all top right diagonal
for j in range(n):
# here we use stack for reversing
# the element of diagonal
s = []
i = row
k = j
while (i < n and k >= 0):
s.append(mat[i][k])
i += 1
k -= 1
# push all element back to matrix
# in reverse order
i = row
k = j
while (i < n and k >= 0):
mat[i][k] = s[-1]
k -= 1
i += 1
s.pop()
# do the same process for all the
# diagonal which start from last
# column
column = n - 1
for j in range(1, n):
# here we use stack for reversing
# the elements of diagonal
s = []
i = j
k = column
while (i < n and k >= 0):
s.append(mat[i][k])
i += 1
k -= 1
# push all element back to matrix
# in reverse order
i = j
k = column
while (i < n and k >= 0):
mat[i][k] = s[-1]
i += 1
k -= 1
s.pop()
# Utility function to pra matrix
def printMatrix(mat, n):
for i in range(n):
for j in range(n):
print(mat[i][j], end=" ")
print()
# Driver code
mat = [[1, 2, 3, 4],[5, 6, 7, 8],
[9, 10, 11, 12],[13, 14, 15, 16]]
n = 4
imageSwap(mat, n)
printMatrix(mat, n)
# This code is contributed by shubhamsingh10
C#
// Simple C# program to find mirror of
// matrix across diagonal.
using System;
using System.Collections.Generic;
class GFG
{
static int MAX = 100;
static void imageSwap(int [,]mat, int n)
{
// for diagonal which start from at
// first row of matrix
int row = 0;
// traverse all top right diagonal
for (int j = 0; j < n; j++)
{
// here we use stack for reversing
// the element of diagonal
Stack<int> s = new Stack<int>();
int i = row, k = j;
while (i < n && k >= 0)
{
s.Push(mat[i++,k--]);
}
// push all element back to matrix
// in reverse order
i = row;
k = j;
while (i < n && k >= 0)
{
mat[i++,k--] = s.Peek();
s.Pop();
}
}
// do the same process for all the
// diagonal which start from last
// column
int column = n - 1;
for (int j = 1; j < n; j++)
{
// here we use stack for reversing
// the elements of diagonal
Stack<int> s = new Stack<int>();
int i = j, k = column;
while (i < n && k >= 0)
{
s.Push(mat[i++,k--]);
}
// push all element back to matrix
// in reverse order
i = j;
k = column;
while (i < n && k >= 0)
{
mat[i++,k--] = s.Peek();
s.Pop();
}
}
}
// Utility function to print a matrix
static void printMatrix(int [,]mat, int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
Console.Write(mat[i,j] + " ");
}
Console.WriteLine("");
}
}
// Driver code
public static void Main(String[] args)
{
int [,]mat = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
int n = 4;
imageSwap(mat, n);
printMatrix(mat, n);
}
}
/* This code contributed by PrinciRaj1992 */
输出:
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16
时间复杂度:O(n * n)
。
此问题的有效解决方案是,如果我们观察到输出矩阵,则注意到我们只需要交换mat[i][j], mat[j][i]
。
以下是上述想法的实现。
C++
// Efficient CPP program to find mirror of
// matrix across diagonal.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
void imageSwap(int mat[][MAX], int n)
{
// traverse a matrix and swap
// mat[i][j] with mat[j][i]
for (int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
mat[i][j] = mat[i][j] + mat[j][i] -
(mat[j][i] = mat[i][j]);
}
// Utility function to print a matrix
void printMatrix(int mat[][MAX], int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << mat[i][j] << " ";
cout << endl;
}
}
// driver program to test above function
int main()
{
int mat[][MAX] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int n = 4;
imageSwap(mat, n);
printMatrix(mat, n);
return 0;
}
Java
// Efficient Java program to find mirror of
// matrix across diagonal.
import java.io.*;
class GFG {
static int MAX = 100;
static void imageSwap(int mat[][], int n)
{
// traverse a matrix and swap
// mat[i][j] with mat[j][i]
for (int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
mat[i][j] = mat[i][j] + mat[j][i]
- (mat[j][i] = mat[i][j]);
}
// Utility function to print a matrix
static void printMatrix(int mat[][], int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
System.out.print( mat[i][j] + " ");
System.out.println();
}
}
// driver program to test above function
public static void main (String[] args)
{
int mat[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int n = 4;
imageSwap(mat, n);
printMatrix(mat, n);
}
}
// This code is contributed by anuj_67.
Python3
# Efficient Python3 program to find mirror of
# matrix across diagonal.
from builtins import range
MAX = 100;
def imageSwap(mat, n):
# traverse a matrix and swap
# mat[i][j] with mat[j][i]
for i in range(n):
for j in range(i + 1):
t = mat[i][j];
mat[i][j] = mat[j][i]
mat[j][i] = t
# Utility function to pra matrix
def printMatrix(mat, n):
for i in range(n):
for j in range(n):
print(mat[i][j], end=" ");
print();
# Driver code
if __name__ == '__main__':
mat = [1, 2, 3, 4], \
[5, 6, 7, 8], \
[9, 10, 11, 12], \
[13, 14, 15, 16];
n = 4;
imageSwap(mat, n);
printMatrix(mat, n);
# This code is contributed by Rajput-Ji
C
// Efficient C# program to find mirror of
// matrix across diagonal.
using System;
class GFG {
//static int MAX = 100;
static void imageSwap(int [,]mat, int n)
{
// traverse a matrix and swap
// mat[i][j] with mat[j][i]
for (int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
mat[i,j] = mat[i,j] + mat[j,i]
- (mat[j,i] = mat[i,j]);
}
// Utility function to print a matrix
static void printMatrix(int [,]mat, int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
Console.Write( mat[i,j] + " ");
Console.WriteLine();
}
}
// driver program to test above function
public static void Main ()
{
int [,]mat = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int n = 4;
imageSwap(mat, n);
printMatrix(mat, n);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// Efficient PHP program to find mirror
// of matrix across diagonal.
function imageSwap(&$mat, $n)
{
// traverse a matrix and swap
// mat[i][j] with mat[j][i]
for ($i = 0; $i < $n; $i++)
for ($j = 0; $j <= $i; $j++)
$mat[$i][$j] = $mat[$i][$j] + $mat[$j][$i] -
($mat[$j][$i] = $mat[$i][$j]);
}
// Utility function to print a matrix
function printMatrix(&$mat, $n)
{
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
{
echo ($mat[$i][$j]);
echo (" ");
}
echo ("\n");
}
}
// Driver Code
$mat = array(array(1, 2, 3, 4),
array(5, 6, 7, 8),
array(9, 10, 11, 12),
array(13, 14, 15, 16));
$n = 4;
imageSwap($mat, $n);
printMatrix($mat, $n);
// This code is contributed
// by Shivi_Aggarwal
?>
输出:
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16
时间复杂度:O(n*n)
。
版权属于:月萌API www.moonapi.com,转载请注明出处