Leetcode-498: diagonal traversal

Title Description

Give you a size of m x n Matrix mat , Please traverse diagonally , Use an array to return all the elements in the matrix .

Example

Example 1：
Input ：nums = [2,7,11,15], target = 9
Output ：[0,1]
explain ： because nums[0] + nums[1] == 9 , return [0, 1] .

Example 2：
Input ：mat = [[1,2],[3,4]]
Output ：[1,2,3,4]

The problem solving process

Ideas and steps

（1）m * n  Two dimensional matrix of ,  All in all  m + n - 1  Diagonals ,  The traversal directions of adjacent diagonals are different ;
（2） Set the number of diagonal from top to bottom as  [0,m + n − 2]. When  i  For even when ,  Traversal direction is from bottom left to top right ; When  i  In an odd number of , The traversal direction is from top right to bottom left ;
（3） When the first  i  Diagonals are traversed from bottom left to top right ,  namely  i  For even when ,  Each row index minus  1,  Column index plus  1,  Up to the edge of the matrix ;
       When  i < m  when ,  At this time, the starting point of diagonal traversal is  (i, 0);
       When  i ≥ m  when , At this time, the starting point of diagonal traversal is  (m − 1, i − m + 1);
（4） When the first  i  Diagonals are traversed from top right to bottom left ,  namely  i  In an odd number of ,  Every time the row index is added  1,  Column index minus  1,  Up to the edge of the matrix ;
       When  i < n  when ,  At this time, the starting point of diagonal traversal is  (0, i);
       When  i ≥ n  when , Then the starting point of diagonal traversal is  (i − n + 1, n − 1);

Code display

public class FindDiagonalOrder {
    

    /** *  Official answer ： * m * n  Two dimensional matrix of ,  All in all  m + n - 1  Diagonals ,  The traversal directions of adjacent diagonals are different  *  Set the number of diagonal from top to bottom as  [0,m + n − 2] *  When  i  For even when ,  Traversal direction is from bottom left to top right ; *  When  i  In an odd number of , The traversal direction is from top right to bottom left ; * *  When the first  i  Diagonals are traversed from bottom left to top right ,  namely  i  For even when ,  Each row index minus  1,  Column index plus  1,  Up to the edge of the matrix ; *  When  i < m  when ,  At this time, the starting point of diagonal traversal is  (i, 0); *  When  i ≥ m  when , At this time, the starting point of diagonal traversal is  (m − 1, i − m + 1); * *  When the first  i  Diagonals are traversed from top right to bottom left ,  namely  i  In an odd number of ,  Every time the row index is added  1,  Column index minus  1,  Up to the edge of the matrix ; *  When  i < n  when ,  At this time, the starting point of diagonal traversal is  (0, i); *  When  i ≥ n  when , Then the starting point of diagonal traversal is  (i − n + 1, n − 1); **/

    public int[] findDiagonalOrder(int[][] mat) {
    
        //  That's ok 
        int m = mat.length;
        //  Column 
        int n = mat[0].length;
        int[] result = new int[m * n];
        int index = 0;
        for (int i = 0; i < m + n - 1; i++) {
    
            if (i % 2 == 0) {
    
                //  The even number of diagonals 
                int row = 0;
                int line = 0;
                if (i < m) {
    
                    row = i;
                }
                if (i >= m) {
    
                    row = m - 1;
                    line = i - m + 1;
                }
                while (row >= 0 && line < n) {
    
                    result[index] = mat[row][line];
                    row--;
                    line++;
                    index++;
                }
            } else {
    
                //  Odd diagonal 
                int row = 0;
                int line = 0;
                if (i < n) {
    
                    line = i;
                }
                if (i >= n) {
    
                    row = i - n + 1;
                    line = n - 1;
                }
                while (row < m && line >= 0) {
    
                    result[index] = mat[row][line];
                    row++;
                    line--;
                    index++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
    
        int[][] mat = {
    {
    1,2,3},
                       {
    4,5,6},
                       {
    7,8,9}};
        int[] result = new FindDiagonalOrder().findDiagonalOrder(mat);
        for (int i = 0; i < result.length; i++) {
    
            System.out.printf("%2d", result[i]);
        }
        System.out.println();
    }

}