logo

שאילתות במטריקס

נתון שני מספרים שלמים m ו-n שמתאר את הסדר m*n של מטריצה יחד עם [][] בְּהַתחָלָה מְמוּלָא עם מספרים שלמים מ 1 עד m*n ברצף ב א סדר עיקרי בשורה . כמו כן יש א מַעֲרָך שְׁאֵלָה[][] מורכב מ ש שאילתות אשר מכיל שְׁלוֹשָׁה מספרים שלמים כל אחד שבו ה רֵאשִׁית מִספָּר שָׁלֵם ט מתאר את סוּג של שאילתה ושל הַבָּא שני מספרים שלמים x ו ו לתאר את שׁוּרָה אוֹ עַמוּדָה זה צריך להיות מוּפעָל . המשימה היא ל תַהֲלִיך אֵלֶה ש שאילתות מניפולציות יחד עם [][]. כֹּל שְׁאֵלָה הוא אחד משלושת הסוגים הבאים:

  • [1xy]: להחליף את x ה' ו ו ה' שורות מחצלות[][].
  • [2xy]: להחליף את x ה' ו ו ה' עמודות של מחצלת[][].
  • [3xy]: להדפיס את אֵלֵמֶנט בְּ- x ה' שורה ו ו ה' עמודה של מחצלת[][].

דוגמאות: 

קֶלֶט: 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

הֶסבֵּר: בתחילה המטריצה ​​היא:
עם[][] = [[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) מרחב

הרעיון הוא לִיצוֹר מטריצה יחד עם [][] של סדר m*n בְּהַתחָלָה מְמוּלָא עם מספרים שלמים מ 1 עד m*n ברצף ב א סדר עיקרי בשורה . לשאילתות של סוג 1 ו 2 כְּלוֹמַר לְהַחלִיף לַחֲצוֹת שורה או עמודה נדרשים והחליפו את כל אחד מהרכיבים שלו. ולשאילתה של סוג 3 כְּלוֹמַר הֶדפֵּס אנו פשוט מדפיסים את האלמנט באינדקס שצוין.

C++
// C++ Program to perform queries in a matrix. #include    using namespace std; // function to swap rows of the matrix. void swapRows(vector<vector<int>> &mat int r1 int r2) {  for (int i = 0; i < mat[0].size(); i++) {  swap(mat[r1][i] mat[r2][i]);  } } // function to swap columns of the matrix. void swapCols(vector<vector<int>> &mat int c1 int c2) {  for (int i = 0; i < mat.size(); i++) {  swap(mat[i][c1] mat[i][c2]);  } } // function to operate queries. void solveQueries(int m int n vector<vector<int>> &query) {  // create a matrix or order m*n filled with  // values from 1 to m*n.  vector<vector<int>> mat(m vector<int>(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.size(); 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 {  cout << mat[query[i][1]][query[i][2]] << ' ';  }  } } int main() {  int m = 3 n = 3;  vector<vector<int>> query = {{1 0 1}  {3 0 0}  {3 1 0}  {2 0 1}  {3 0 0}  {3 1 0}};  solveQueries(m n query);  return 0; } 
Java
// 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
# 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#
// 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
// 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 

מורכבות זמן: O(q*n) נדרש לביצוע שאילתות q מסוג 1 ו-2.
מרחב עזר: O(m*n) מרחב עזר הנדרש ליצירת מטריצה יחד עם [][] מסדר מ*נ.

[גישה צפויה] - O(q) זמן ו-O(m + n) מרחב

ה אֵלֵמֶנט בכל עמדה מחצלת[x][y] במטריצה ​​ניתן לתאר כ-mat[x][y] = (n*x) + y + 1 אֵיפֹה נ הוא הספירה של עמודות . במקום לשנות את המטריצה ​​ישירות אנחנו יכולים להשתמש דוּ עזר מערכים שורות[m] ו cols[n] . ה שורות מערך הוא אתחול עם ערכים מ אֶל m-1 המייצגים את המדדים של השורות וה- קולס מערך הוא אתחול עם ערכים מ אֶל n-1 המייצגים את המדדים של העמודות.

לעיבוד שאילתה של סוג 1 אשר מחליפים שורות x ו ו אנחנו פשוט לְהַחלִיף את ערכים שֶׁל שורות[x] ו שורות[y]. באופן דומה עבור שאילתה של סוג 2 אשר מחליפים עמודות x ו ו אָנוּ לְהַחלִיף את ערכים שֶׁל cols[x] ו cols[y] . לשאילתה של סוג 3 אֵיזֶה הֶדפֵּס את עֵרֶך בעמדה (x y) אנו מחשבים את המיקום באמצעות הנוסחה mat[x][y] = שורות[x]*n + cols[y] + 1.

להלן יישום הרעיון לעיל:

C++
// C++ Program to perform queries in a matrix. #include    using namespace std; // function to operate queries. void solveQueries(int m int n vector<vector<int>> &query) {  // create two arrays rows and cols  // and fill the value from 0 to size-1  vector<int> rows(m) cols(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.size(); i++) {  // if query is of type 1  // swap the rows.  if (query[i][0] == 1) {  swap(rows[query[i][1]] rows[query[i][2]]);  }  // if query is of type 2  // swap the columns.  else if (query[i][0] == 2) {  swap(cols[query[i][1]] cols[query[i][2]]);  }  // if query is of type 3  // print the value at the given index.  else {  cout<< (rows[query[i][1]] * n) + cols[query[i][2]] + 1 << ' ';  }  } } int main() {  int m = 3 n = 3;  vector<vector<int>> query = {{1 0 1}  {3 0 0}  {3 1 0}  {2 0 1}  {3 0 0}  {3 1 0}};  solveQueries(m n query);  return 0; } 
Java
// 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
# 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#
// 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
// 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) מרחב עזר נדרש ליצירת שני מערכים.