對角線遍歷

給定一個含有 M x N 個元素的矩陣（M 行，N 列），請以對角線遍歷的順序返回這個矩陣中的所有元素，對角線遍歷如下圖所示。

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
      

        
        // Check for empty matrices
        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }
        
        // Variables to track the size of the matrix
        int N = matrix.length;
        int M = matrix[0].length;
        
        // The two arrays as explained in the algorithm
        int[] result = new int[N*M];
        int k = 0;
        ArrayList<Integer> intermediate = new ArrayList<Integer>();
        
        // We have to go over all the elements in the first
        // row and the last column to cover all possible diagonals
        for (int d = 0; d < N + M - 1; d++) {
            
            // Clear the intermediate array every time we start
            // to process another diagonal
            intermediate.clear();
            
            // We need to figure out the "head" of this diagonal
            // The elements in the first row and the last column
            // are the respective heads.
            int r = d < M ? 0 : d - M + 1;
            int c = d < M ? d : M - 1;
            
            // Iterate until one of the indices goes out of scope
            // Take note of the index math to go down the diagonal
            while (r < N && c > -1) {
                
                intermediate.add(matrix[r][c]);
                ++r;
                --c;
            }
                
            // Reverse even numbered diagonals. The
            // article says we have to reverse odd 
            // numbered articles but here, the numbering
            // is starting from 0 :P
            if (d % 2 == 0) {
                Collections.reverse(intermediate);
            }
            
            for (int i = 0; i < intermediate.size(); i++) {
                result[k++] = intermediate.get(i);
            }
        }
        return result;
    }
}

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {

        // 特判，檢查空矩陣
        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }

        // 矩陣的大小：M 行 N 列
        int M = matrix.length;
        int N = matrix[0].length;

        int[] res = new int[M * N]; // 宣告長度爲 m * n 用於儲存結果的一維陣列
        int sign = 0; // 標記對角線的條數，用於翻轉奇數對角線上的元素順序
        int count = 0; // res陣列的動態索引，遍歷一條對角線就儲存於res陣列中

        for (int i = 0; i < (M + N - 1); i++) {
            sign++;
            // 根據行列切換的條件i < N，對x，y賦不同值
            int x = i < N ? 0 : (i + 1 - N);
            int y = i < N ? i : N - 1;
            int fromIndex = count; // 用於翻轉res中新新增的奇數對角線元素的起始索引
            while (x < M & y >= 0) {
                res[count] = matrix[x][y];
                x++;
                y--;
                count++;
            }
            if (sign % 2 == 1) { // 奇數時翻轉
                reverse(res, fromIndex, count);
            }
        }
        return res;
    }

    public void reverse(int[] arr, int fromIndex, int toIndex) {
        /**
        * arr: 需要翻轉的陣列 
        * fromIndex: 指定開始翻轉的陣列的索引位置
        * toIndex:翻轉範圍的最後索引位置（注意不包括索引爲toIndex的元素）
        */
       for (int i = 0; i < ((toIndex - fromIndex) >> 1); i++) {
            int temp = arr[fromIndex + i];
            arr[fromIndex + i] = arr[toIndex - 1 - i];
            arr[toIndex - 1 - i] = temp;
        }
    }
}