当前位置:网站首页>leetCode-498: 對角線遍曆

leetCode-498: 對角線遍曆

2022-06-24 10:14:00 文醜顏不良啊

題目描述

給你一個大小為 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();
    }

}
原网站

版权声明
本文为[文醜顏不良啊]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/175/202206240916244895.html