두 개의 정수가 주어지면 m과 n 순서를 설명하는 것 m*n 행렬의 [][]와 함께 처음에는 채우는 정수로 1 ~ m*n 순차적으로 행 주요 순서 . 또한 2D 정렬 질문[][] 로 구성된 큐 쿼리 다음을 포함하는 삼 각각의 정수 첫 번째 정수 티 설명합니다 유형 쿼리와 다음 두 개의 정수 엑스 그리고 그리고 설명하다 열 또는 열 그게 필요해 움직이는 . 과제는 프로세스 이것들 큐 쿼리 조작 [][]와 함께. 모든 질문 다음 세 가지 유형 중 하나입니다.
- [1xy]: 교환하다 엑스 일 그리고 그리고 일 mat[][]의 행.
- [2xy]: 교환하다 엑스 일 그리고 그리고 일 mat[][]의 열입니다.
- [3xy]: 인쇄하다 요소 ~에 엑스 일 행과 그리고 일 mat[][]의 열입니다.
예:
입력: m = 3 n = 3
쿼리[][] = [[1 0 1]
[3 0 0]
[3 1 0]
[2 0 1]
[3 0 0]
[3 1 0]]산출: 4 1 5 2
설명: 처음에 매트릭스는 다음과 같습니다.
with[][] = [[1 2 3]
[4 5 6]
[7 8 9]]
첫 번째 작업 [1 0 1] : 행 0과 행 1을 바꿔야 합니다.
이 연산 행렬은 다음과 같습니다.
와[][] =[[4 5 6]
[1 2 3]
[7 8 9]]
다음 두 작업에서는 주어진 셀의 요소를 인쇄해야 합니다.
네 번째 연산 [2 0 1]: 열 0과 열 1을 바꿔야 합니다.
이 연산 행렬은 다음과 같습니다.
와[][] =[[5 4 6]
[2 1 3]
[8 7 9]]
다음 두 작업에서는 주어진 셀의 요소를 인쇄해야 합니다.
목차
[순진한 접근 방식] - O(q*n) 시간과 O(m*n) 공간
C++아이디어는 만들다 행렬 [][]와 함께 질서의 m*n 처음에는 채우는 정수로 1 ~ m*n 순차적으로 행 주요 순서 . 쿼리에 대한 유형 1 그리고 2 즉. 교환 횡단 필요한 행 또는 열을 선택하고 각 요소를 바꿉니다. 그리고 쿼리에 대한 유형 3 즉. 인쇄 우리는 단순히 지정된 인덱스에 요소를 인쇄합니다.
// C++ Program to perform queries in a matrix. #include
// Java Program to perform queries in a matrix. import java.util.*; class GfG { // function to swap rows of the matrix. static void swapRows(int[][] mat int r1 int r2) { for (int i = 0; i < mat[0].length; i++) { int temp = mat[r1][i]; mat[r1][i] = mat[r2][i]; mat[r2][i] = temp; } } // function to swap columns of the matrix. static void swapCols(int[][] mat int c1 int c2) { for (int i = 0; i < mat.length; i++) { int temp = mat[i][c1]; mat[i][c1] = mat[i][c2]; mat[i][c2] = temp; } } // function to operate queries. static void solveQueries(int m int n int[][] query) { // create a matrix or order m*n filled with // values from 1 to m*n. int[][] mat = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { mat[i][j] = (i * n) + j + 1; } } // perform the queries on the matrix. for (int i = 0; i < query.length; i++) { // if query is of type 1 // swap the rows. if (query[i][0] == 1) { swapRows(mat query[i][1] query[i][2]); } // if query is of type 2 // swap the columns. else if (query[i][0] == 2) { swapCols(mat query[i][1] query[i][2]); } // if query is of type 3 // print the value at the given index. else { System.out.print(mat[query[i][1]][query[i][2]] + ' '); } } } public static void main(String[] args) { int m = 3 n = 3; int[][] query = { {1 0 1} {3 0 0} {3 1 0} {2 0 1} {3 0 0} {3 1 0} }; solveQueries(m n query); } }
# Python Program to perform queries in a matrix. # function to swap rows of the matrix. def swapRows(mat r1 r2): mat[r1] mat[r2] = mat[r2] mat[r1] # function to swap columns of the matrix. def swapCols(mat c1 c2): for row in mat: row[c1] row[c2] = row[c2] row[c1] # function to operate queries. def solveQueries(m n query): # create a matrix of order m*n filled with # values from 1 to m*n. mat = [[(i * n) + j + 1 for j in range(n)] for i in range(m)] # perform the queries on the matrix. for q in query: # if query is of type 1 # swap the rows. if q[0] == 1: swapRows(mat q[1] q[2]) # if query is of type 2 # swap the columns. elif q[0] == 2: swapCols(mat q[1] q[2]) # if query is of type 3 # print the value at the given index. else: print(mat[q[1]][q[2]] end=' ') if __name__ == '__main__': m n = 3 3 query = [ [1 0 1] [3 0 0] [3 1 0] [2 0 1] [3 0 0] [3 1 0] ] solveQueries(m n query)
// C# Program to perform queries in a matrix. using System; class GfG { // function to swap rows of the matrix. static void SwapRows(int[] mat int r1 int r2) { for (int i = 0; i < mat.GetLength(1); i++) { int temp = mat[r1 i]; mat[r1 i] = mat[r2 i]; mat[r2 i] = temp; } } // function to swap columns of the matrix. static void SwapCols(int[] mat int c1 int c2) { for (int i = 0; i < mat.GetLength(0); i++) { int temp = mat[i c1]; mat[i c1] = mat[i c2]; mat[i c2] = temp; } } // function to operate queries. static void SolveQueries(int m int n int[][] query) { // create a matrix or order m*n filled with // values from 1 to m*n. int[] mat = new int[m n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { mat[i j] = (i * n) + j + 1; } } // perform the queries on the matrix. for (int i = 0; i < query.Length; i++) { // if query is of type 1 // swap the rows. if (query[i][0] == 1) { SwapRows(mat query[i][1] query[i][2]); } // if query is of type 2 // swap the columns. else if (query[i][0] == 2) { SwapCols(mat query[i][1] query[i][2]); } // if query is of type 3 // print the value at the given index. else { Console.Write(mat[query[i][1] query[i][2]] + ' '); } } } static void Main(string[] args) { int m = 3 n = 3; int[][] query = { new int[] { 1 0 1 } new int[] { 3 0 0 } new int[] { 3 1 0 } new int[] { 2 0 1 } new int[] { 3 0 0 } new int[] { 3 1 0 } }; SolveQueries(m n query); } }
// JavaScript Program to perform queries in a matrix. // function to swap rows of the matrix. function swapRows(mat r1 r2) { [mat[r1] mat[r2]] = [mat[r2] mat[r1]]; } // function to swap columns of the matrix. function swapCols(mat c1 c2) { for (let i = 0; i < mat.length; i++) { [mat[i][c1] mat[i][c2]] = [mat[i][c2] mat[i][c1]]; } } // function to operate queries. function solveQueries(m n query) { // create a matrix or order m*n filled with // values from 1 to m*n. const mat = Array.from({ length: m } (_ i) => Array.from({ length: n } (_ j) => i * n + j + 1) ); // perform the queries on the matrix. for (const q of query) { // if query is of type 1 // swap the rows. if (q[0] === 1) { swapRows(mat q[1] q[2]); } // if query is of type 2 // swap the columns. else if (q[0] === 2) { swapCols(mat q[1] q[2]); } // if query is of type 3 // print the value at the given index. else { console.log(mat[q[1]][q[2]] + ' '); } } } // driver code const m = 3 n = 3; const query = [ [1 0 1] [3 0 0] [3 1 0] [2 0 1] [3 0 0] [3 1 0] ]; solveQueries(m n query);
산출
4 1 5 2
시간 복잡도: 유형 1과 2의 q 쿼리를 수행하려면 O(q*n)이 필요합니다.
보조 공간: 행렬 생성에 필요한 O(m*n) 보조 공간 [][]와 함께 m*n 차수입니다.
[예상 접근법] - O(q) 시간과 O(m + n) 공간
그만큼 요소 어느 위치에서나 매트[x][y] 행렬에서 mat[x][y] =로 설명할 수 있습니다. (n*x) + y + 1 어디 N 의 개수입니다 기둥 . 행렬을 직접 수정하는 대신 다음을 사용할 수 있습니다. 둘 보조자 행 배열[m] 그리고 열[n] . 그만큼 행 배열은 초기화됨 다음 값으로 에게 m-1 행의 인덱스를 나타냅니다. 열 배열은 초기화됨 다음 값으로 에게 n-1 열의 인덱스를 나타냅니다.
쿼리를 처리하려면 유형 1 교환하는 것 행 엑스 그리고 그리고 우리는 단순히 교환 그만큼 가치 ~의 행[x] 그리고 행[y]. 마찬가지로 쿼리의 경우 유형 2 교환하는 것 기둥 엑스 그리고 그리고 우리 교환 그만큼 가치 ~의 열[x] 그리고 열[y] . 쿼리에 대한 유형 3 어느 인쇄 그만큼 값 위치에 (xy) 우리는 공식을 사용하여 위치를 계산합니다 mat[x][y] = 행[x]*n + 열[y] + 1.
다음은 위의 아이디어를 구현한 것입니다.
C++// C++ Program to perform queries in a matrix. #include
// Java Program to perform queries in a matrix. import java.util.*; class GfG { // function to operate queries. static void solveQueries(int m int n int[][] query) { // create two arrays rows and cols // and fill the value from 0 to size-1 int[] rows = new int[m]; int[] cols = new int[n]; for (int i = 0; i < m; i++) { rows[i] = i; } for (int i = 0; i < n; i++) { cols[i] = i; } // perform the queries on the matrix. for (int i = 0; i < query.length; i++) { // if query is of type 1 // swap the rows. if (query[i][0] == 1) { int temp = rows[query[i][1]]; rows[query[i][1]] = rows[query[i][2]]; rows[query[i][2]] = temp; } // if query is of type 2 // swap the columns. else if (query[i][0] == 2) { int temp = cols[query[i][1]]; cols[query[i][1]] = cols[query[i][2]]; cols[query[i][2]] = temp; } // if query is of type 3 // print the value at the given index. else { System.out.print((rows[query[i][1]]*n + cols[query[i][2]] + 1) + ' '); } } } public static void main(String[] args) { int m = 3 n = 3; int[][] query = { {1 0 1} {3 0 0} {3 1 0} {2 0 1} {3 0 0} {3 1 0} }; solveQueries(m n query); } }
# Python Program to perform queries in a matrix. # function to operate queries. def solveQueries(m n query): # create two arrays rows and cols # and fill the value from 0 to size-1 rows = [i for i in range(m)] cols = [i for i in range(n)] # perform the queries on the matrix. for q in query: # if query is of type 1 # swap the rows. if q[0] == 1: rows[q[1]] rows[q[2]] = rows[q[2]] rows[q[1]] # if query is of type 2 # swap the columns. elif q[0] == 2: cols[q[1]] cols[q[2]] = cols[q[2]] cols[q[1]] # if query is of type 3 # print the value at the given index. else: print((rows[q[1]] * n) + cols[q[2]] + 1 end=' ') if __name__ == '__main__': m n = 3 3 query = [ [1 0 1] [3 0 0] [3 1 0] [2 0 1] [3 0 0] [3 1 0] ] solveQueries(m n query)
// C# Program to perform queries in a matrix. using System; class GfG { // function to operate queries. static void SolveQueries(int m int n int[][] query) { // create two arrays rows and cols // and fill the value from 0 to size-1 int[] rows = new int[m]; int[] cols = new int[n]; for(int i = 0; i < m; i++) { rows[i] = i; } for(int i = 0; i < n; i++) { cols[i] = i; } // perform the queries on the matrix. for (int i = 0; i < query.Length; i++) { // if query is of type 1 // swap the rows. if (query[i][0] == 1) { int temp = rows[query[i][1]]; rows[query[i][1]] = rows[query[i][2]]; rows[query[i][2]] = temp; } // if query is of type 2 // swap the columns. else if (query[i][0] == 2) { int temp = cols[query[i][1]]; cols[query[i][1]] = cols[query[i][2]]; cols[query[i][2]] = temp; } // if query is of type 3 // print the value at the given index. else { Console.Write((rows[query[i][1]]*n + cols[query[i][2]] + 1) + ' '); } } } static void Main(string[] args) { int m = 3 n = 3; int[][] query = { new int[] { 1 0 1 } new int[] { 3 0 0 } new int[] { 3 1 0 } new int[] { 2 0 1 } new int[] { 3 0 0 } new int[] { 3 1 0 } }; SolveQueries(m n query); } }
// JavaScript Program to perform queries in a matrix. // function to operate queries. function solveQueries(m n query) { // create two arrays rows and cols // and fill the value from 0 to size-1 let rows = new Array(m); let cols = new Array(n); for (let i = 0; i < m; i++) { rows[i] = i; } for (let i = 0; i < n; i++) { cols[i] = i; } // perform the queries on the matrix. for (const q of query) { // if query is of type 1 // swap the rows. if (q[0] === 1) { [rows[q[1]] rows[q[2]]] = [rows[q[2]] rows[q[1]]]; } // if query is of type 2 // swap the columns. else if (q[0] === 2) { [cols[q[1]] cols[q[2]]] = [cols[q[2]] cols[q[1]]]; } // if query is of type 3 // print the value at the given index. else { process.stdout.write(((rows[q[1]] * n) + cols[q[2]] + 1) + ' '); } } } const m = 3 n = 3; const query = [ [1 0 1] [3 0 0] [3 1 0] [2 0 1] [3 0 0] [3 1 0] ]; solveQueries(m n query);
산출
4 1 5 2
시간 복잡도: O(q) q = 쿼리 수
보조 공간: 두 개의 어레이를 생성하려면 O(m + n)개의 보조 공간이 필요합니다.