矩阵对角线的镜像

原文: 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)