Печатать граничные элементы заданной матрицы по часовой стрелке
Для матрицы arr [] [] размера N * M задача состоит в том, чтобы вывести граничные элементы данной матрицы в виде по часовой стрелке.
Примеры:
Input: arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9} }
Output: 1 2 3 6 9 8 7 4
Explanation:
Boundary elements of the matrix are:
1 2 3
4 5 6
7 8 <strong>9
Therefore, the sequence of boundary elements in clockwise form is {1, 2, 3, 6, 9, 8, 7, 4}.
Input: arr[][] = {{11, 12, 33}, {64, 57, 61}, {74, 88, 39}}
Output: 11 12 33 61 39 88 74 64
Наивный подход: Простейший подход к решению этой проблемы - пройти по заданной матрице и проверить, является ли текущий элемент граничным элементом или нет. Если обнаружено, что это правда, то распечатайте элемент.
Сложность времени: O (N 2 )
Вспомогательное пространство: O (1)
Эффективный подход: для оптимизации описанного выше подхода идея состоит в том, чтобы пройти только первую и последнюю строки, а также первый и последний столбцы матрицы. Выполните следующие действия, чтобы решить проблему:
- Выведите первую строку матрицы.
- Выведите последний столбец матрицы, кроме первой строки.
- Выведите последнюю строку матрицы, кроме последнего столбца.
- Выведите первый столбец матрицы, кроме первой и последней строки.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to print the boundary elements // of the matrix in clockwise void boundaryTraversal(vector<vector< int > > arr, int N, int M) { // Print the first row for ( int i = 0; i < M; i++) { cout << arr[0][i] << " " ; } // Print the last column // except the first row for ( int i = 1; i < N; i++) { cout << arr[i][M - 1] << " " ; } // Print the last row // except the last column if (N > 1) { // Print the last row for ( int i = M - 2; i >= 0; i--) { cout << arr[N - 1][i] << " " ; } } // Print the first column except // the first and last row if (M > 1) { // Print the first column for ( int i = N - 2; i > 0; i--) { cout << arr[i][0] << " " ; } } } // Driver Code int main() { vector<vector< int > > arr{ { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int N = arr.size(); int M = arr[0].size(); // Function Call boundaryTraversal(arr, N, M); return 0; } // This code is contributed by Dharanendra L V |
Java
// Java program of the above approach import java.util.*; class GFG { // Function to print the boundary elements // of the matrix in clockwise public static void boundaryTraversal( int arr[][], int N, int M) { // Print the first row for ( int i = 0 ; i < M; i++) { System.out.print(arr[ 0 ][i] + " " ); } // Print the last column // except the first row for ( int i = 1 ; i < N; i++) { System.out.print(arr[i][M - 1 ] + " " ); } // Print the last row // except the last column if (N > 1 ) { // Print the last row for ( int i = M - 2 ; i >= 0 ; i--) { System.out.print(arr[N - 1 ][i] + " " ); } } // Print the first column except // the first and last row if (M > 1 ) { // Print the first column for ( int i = N - 2 ; i > 0 ; i--) { System.out.print(arr[i][ 0 ] + " " ); } } } // Driver Code public static void main(String[] args) { int arr[][] = { { 1 , 2 , 3 }, { 4 , 5 , 6 }, { 7 , 8 , 9 } }; int N = arr.length; int M = arr[ 0 ].length; // Function Call boundaryTraversal(arr, N, M); } } |
Python3
# Python program of the above approach # Function to print the boundary elements # of the matrix in clockwise def boundaryTraversal(arr, N, M): # Print the first row for i in range (M): print (arr[ 0 ][i], end = " " ); # Print the last column # except the first row for i in range ( 1 , N): print (arr[i][M - 1 ], end = " " ); # Print the last row # except the last column if (N > 1 ): # Print the last row for i in range (M - 2 , - 1 , - 1 ): print (arr[N - 1 ][i], end = " " ); # Print the first column except # the first and last row if (M > 1 ): # Print the first column for i in range (N - 2 , 0 , - 1 ): print (arr[i][ 0 ], end = " " ); # Driver Code if __name__ = = "__main__" : arr = [[ 1 , 2 , 3 ], [ 4 , 5 , 6 ], [ 7 , 8 , 9 ]]; N = len (arr); M = len (arr[ 0 ]); # Function Call boundaryTraversal(arr, N, M); # This code is contributed by 29AjayKumar |
C#
// C# program of the above approach using System; class GFG{ // Function to print the boundary elements // of the matrix in clockwise static void boundaryTraversal( int [,] arr, int N, int M) { // Print the first row for ( int i = 0; i < M; i++) { Console.Write(arr[0, i] + " " ); } // Print the last column // except the first row for ( int i = 1; i < N; i++) { Console.Write(arr[i, M - 1] + " " ); } // Print the last row // except the last column if (N > 1) { // Print the last row for ( int i = M - 2; i >= 0; i--) { Console.Write(arr[N - 1, i] + " " ); } } // Print the first column except // the first and last row if (M > 1) { // Print the first column for ( int i = N - 2; i > 0; i--) { Console.Write(arr[i, 0] + " " ); } } } // Driver code static void Main() { int [,] arr = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int N = 3; int M = 3; // Function Call boundaryTraversal(arr, N, M); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program of the above approach // Function to print the boundary elements // of the matrix in clockwise function boundaryTraversal(arr, N, M) { // Print the first row for (let i = 0; i < M; i++) { document.write(arr[0][i] + " " ); } // Print the last column // except the first row for (let i = 1; i < N; i++) { document.write(arr[i][M - 1] + " " ); } // Print the last row // except the last column if (N > 1) { // Print the last row for (let i = M - 2; i >= 0; i--) { document.write(arr[N - 1][i] + " " ); } } // Print the first column except // the first and last row if (M > 1) { // Print the first column for (let i = N - 2; i > 0; i--) { document.write(arr[i][0] + " " ); } } } // Driver Code let arr = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]; let N = arr.length; let M = arr[0].length; // Function Call boundaryTraversal(arr, N, M); </script> |
1 2 3 6 9 8 7 4
Сложность времени: O (N + M)
Вспомогательное пространство: O (1)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.