The programming task is to implement a function that takes a matrix of size m x n, and returns all elements of the matrix in diagonal traversal order as an array.
Input example: mat = [[1,2,3],[4,5,6],[7,8,9]]Output example: [1,2,4,7,5,3,6,8,9]Example 2:Input example: mat = [[1,2],[3,4]]Output example: [1,2,3,4]Start solving the problem
Thoughts and Algorithm
The sum of the coordinates (x, y) of the elements in each diagonal is increasing.
First diagonal: The coordinate of 1 is (0, 0). x + y == 0.
Second diagonal: The coordinates of 2 is (1, 0), and 4 is (0, 1). x + y == 1.
Third diagonal: The coordinates of 7 is (0, 2), 5 is (1, 1), and 3 is (2, 0). For the third diagonal, x + y == 2.
Fourth diagonal: …
In each diagonal, either x or y decreases (each time -1), while the other increases (each time +1).
Second diagonal: The coordinates of 2 is (1, 0), and 4 is (0, 1). x decreases by 1 each time, y increases by 1 each time.
Third diagonal: The coordinates of 7 is (0, 2), 5 is (1, 1), and 3 is (2, 0). x increases by 1 each time, y decreases by 1 each time.
Determine the initial values. For example, in this diagonal, x decreases, and we try to take the maximum for x. When the initial value exceeds the upper limit of x, the deficit is added to y.
Second diagonal: The coordinates of 2 is (1, 0), and 4 is (0, 1). x + y == 1, initial value for x is 1, y is 0.
Fourth diagonal: The coordinates of 6 is (2, 1), and 8 is (1, 2). x + y == 3, initial value for x is 2, the remainder is added to y, y is 1.
Determine the end values. For example, in this diagonal where x decreases, the end condition is when x reaches 0 or y reaches the upper limit.
Second diagonal: The coordinates of 2 is (1, 0), and 4 is (0, 1). Stop when x reaches 0.
Fourth diagonal: The coordinates of 6 is (2, 1), and 8 is (1, 2). Although x only decreases to 1, y has already reached the upper limit.
This diagonal has x decreasing, so the next diagonal will have y decreasing, and this process continues. When the direction is reversed, the logical processing is the same, except that x, y and their respective upper limits are reversed.
x decreases, second diagonal: The coordinates of 2 is (1, 0), and 4 is (0, 1). x + y == 1, initial value for x is 1, y is 0. End condition is when x reaches 0.
x increases, third diagonal: The coordinates of 7 is (0, 2), 5 is (1, 1), and 3 is (2, 0). x + y == 2, initial value for y is 2, x is 0. End condition is when y reaches 0.
Further optimizationNo matter the direction of this diagonal, the logical processing is the same, so writing two similar pieces of code can be cumbersome; try to merge them into one.bool bXFlag = true;Use a boolean flag to correctly position the data used. For example:// 5. The logical processing is the same, the upper limits of x and y are reversedint pm = bXFlag ? m : n;int pn = bXFlag ? n : m;This ensures that the logical calculation code is the same, while the data is different.Each diagonal is treated as a unit, so i represents the sum of each diagonal.// 1. The sum of coordinates (x, y) is increasingfor (int i = 0; i < m + n; i++)Based on the pattern, we can determine the initial values of x and y.// 3. When the initial value exceeds the upper limit of x, the deficit is added to y.int x = (i < pm) ? i : pm – 1;int y = i – x;End condition for each diagonal.// 4. The end condition for this diagonal is when x reaches 0 or y reaches the upper limit.while (x >= 0 && y < pn)Within a diagonal, x and y change.// 2. Each diagonal has either x or y decreasing (each time -1), while the other increases (each time +1).x–; y++;Output the numbers. Note the change based on the flag.// 5. When the direction is reversed, x and y are reversed.nums.push_back(bXFlag ? matrix[x][y] : matrix[y][x]);The diagonal ends here, loop back, and change the flag.bXFlag = !bXFlag;
The C++ implementation is as follows:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) { vector<int> nums; int m = matrix.size(); if (m == 0) return nums; int n = matrix[0].size(); if (n == 0) return nums; bool bXFlag = true; for (int i = 0; i < m + n; i++) { int pm = bXFlag ? m : n; int pn = bXFlag ? n : m; int x = (i < pm) ? i : pm - 1; int y = i - x; while (x >= 0 && y < pn) { nums.push_back(bXFlag ? matrix[x][y] : matrix[y][x]); x--; y++; } bXFlag = !bXFlag; } return nums; } </int></vector<int></int>