leetCode-498: 對角線遍曆

題目描述

給你一個大小為 m x n 的矩陣 mat ，請以對角線遍曆的順序，用一個數組返回這個矩陣中的所有元素。

示例

示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
輸入：mat = [[1,2],[3,4]]
輸出：[1,2,3,4]

解題過程

思路及步驟

（1）m * n 的二維矩陣, 總共有 m + n - 1 條對角線, 相鄰的對角線的遍曆方向不同；
（2）設對角線從上到下的編號為 [0,m + n − 2]。當 i 為偶數時, 遍曆方向為從左下向右上遍曆;當 i 為奇數時，遍曆方向為從右上向左下遍曆;
（3）當第 i 條對角線為從左下向右上遍曆時, 即 i 為偶數時, 每次行索引减 1, 列索引加 1, 直到矩陣的邊緣為止;
      當 i < m 時, 此時對角線遍曆的起點比特置為 (i, 0);
      當 i ≥ m 時，此時對角線遍曆的起點比特置為 (m − 1, i − m + 1);
（4）當第 i 條對角線為從右上向左下遍曆時, 即 i 為奇數時, 每次行索引加 1, 列索引减 1, 直到矩陣的邊緣為止;
      當 i < n 時, 此時對角線遍曆的起點比特置為 (0, i);
      當 i ≥ n 時，則此時對角線遍曆的起點比特置為 (i − n + 1, n − 1);

代碼展示

public class FindDiagonalOrder {
    

    /** * 官方解答： * m * n 的二維矩陣, 總共有 m + n - 1 條對角線, 相鄰的對角線的遍曆方向不同 * 設對角線從上到下的編號為 [0,m + n − 2] * 當 i 為偶數時, 遍曆方向為從左下向右上遍曆; * 當 i 為奇數時，遍曆方向為從右上向左下遍曆; * * 當第 i 條對角線為從左下向右上遍曆時, 即 i 為偶數時, 每次行索引减 1, 列索引加 1, 直到矩陣的邊緣為止; * 當 i < m 時, 此時對角線遍曆的起點比特置為 (i, 0); * 當 i ≥ m 時，此時對角線遍曆的起點比特置為 (m − 1, i − m + 1); * * 當第 i 條對角線為從右上向左下遍曆時, 即 i 為奇數時, 每次行索引加 1, 列索引减 1, 直到矩陣的邊緣為止; * 當 i < n 時, 此時對角線遍曆的起點比特置為 (0, i); * 當 i ≥ n 時，則此時對角線遍曆的起點比特置為 (i − n + 1, n − 1); **/

    public int[] findDiagonalOrder(int[][] mat) {
    
        // 行
        int m = mat.length;
        // 列
        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) {
    
                // 第偶數條對角線
                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 {
    
                // 第奇數條對角線
                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();
    }

}