首页 > 试题广场 >

对角线遍历矩阵

[编程题]对角线遍历矩阵
  • 热度指数：1214 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个大小为 n*m 的矩阵，请以对角线遍历并返回遍历结果

数据范围： ，矩阵中的元素满足
示例1

输入

[[1,2,3],[4,5,6],[7,8,9]]

输出

[1,2,4,7,5,3,6,8,9]
示例2

输入

[[1,3],[2,4]]

输出

[1,3,2,4]
算法知识视频讲解
添加回答
Java
刻苦的大熊猫在度假头像 刻苦的大熊猫在度假
java 简单点，遍历对角线模拟 
public int[] diagonalOrder (int[][] mat) {
        // write code here
        int m = mat.length, n = mat[0].length;
        int[] matrix = new int[m*n];
        int idx = 0;
        // 共有m+n-1条对角线，
        for(int i=0;i<m+n;i++){
            if(i%2 == 0){
                // 当该对角线的下标为偶数时，从下往上遍历 x向上遍历y向右遍历
                // i<m 此时的起点为 (i, 0) i>=m 此时的起点为（m-1, i-m+1）
                int x = i<m?i:m-1;
                int y = i<m?0:i-m+1;
                while(x>=0 && y<n){
                    matrix[idx++] = mat[x--][y++];
                }
            }else{
                // 从上往下遍历 横坐标向下移动 纵坐标向左移动
                // i<n 起点为(0, i) i>=n时 起点为(i-n+1, n-1)
                int x = i<n?0:i-n+1;
                int y = i<n?i:n-1;
                while(x<m && y>=0){
                    matrix[idx++] = mat[x++][y--];
                }
            }
        }
        return matrix;
    }


发表于 2022-07-28 10:16:10 回复(0)
Java
ngcmz7头像 ngcmz7 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型二维数组 
     * @return int整型一维数组
     */

    public int[] diagonalOrder (int[][] mat) {

        int[] startPoint = new int[]{-1,0};
        List<Integer> list= new ArrayList<>();
        boolean upToDown = false;
        while(list.size()!=mat.length*mat[0].length) {
            if(!upToDown){
                //左下往右上
                startPoint = up(list,startPoint[0],startPoint[1],mat);
                upToDown=true;
            }else{
                //右上往左下
                startPoint = down(list,startPoint[0],startPoint[1],mat);
                upToDown=false;
            }
        }
        
        int[] result = new int[list.size()];
        for(int i=0; i<result.length; i++) {
            result[i]=list.get(i);
        }
        return result;
    }
    
    public int[] up(List<Integer> list, int i, int j, int[][] mat) {
         //如果到下边界则往右走
        if(i==mat.length-1) j+=1;
        else i+=1;//如果还没到下边界则继续往下走
         
        while(i>=0 && j<mat[0].length){
            list.add(mat[i--][j++]);
        }
        
        //i和j确保返回的i，j不会超出边界
        i++;
        j--;
        return new int[]{i,j};
    }
    
    public int[] down(List<Integer> list, int i, int j, int[][] mat) {
        //如果到右边界则往下走
        if(j==mat[0].length-1) i+=1;
        else j+=1;//如果还没到右边界则继续往右走
         
        while(i<mat.length && j>=0){
            list.add(mat[i++][j--]);
        }
        //i和j确保返回的i，j不会超出边界
        i--;
        j++;
        return new int[]{i,j};
    }
}

发表于 2022-03-24 18:43:48 回复(0)
Java
pein531头像 pein531

双指针流程

指定两个指针p1和p2从mat[0][0]位置出发，两个指针同步移动，不存在一个走另一个不走的情况：
  1. p1一直往右走，直到碰到右边界就往下走；
  2. p2一直往下走，直到碰到左边界就往右走。
两个指针每次移动都能确定矩阵的一条对角斜线，根据操作的奇偶性，每次按照从右上到左下或从左下到右上将矩阵元素追加到链表中即可。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型二维数组 
     * @return int整型一维数组
     */
    public int[] diagonalOrder (int[][] mat) {
        // write code here
        int n = mat.length, m = mat[0].length;
        LinkedList<Integer> list = new LinkedList<>();
        int row1 = 0, col1 = 0;
        int row2 = 0, col2 = 0;
        boolean flag = false;
        list.add(mat[0][0]);
        while(row1 < n && col2 < m){
            if(col1 + 1 < m){
                col1 ++;     // 还没到右边界就往右走
            }else{
                row1 ++;     // 到了右边界就往下走
            }
            if(row2 + 1 < n){
                row2 ++;     // 还没到下边界就往下走
            }else{
                col2++;      // 到了下边界就往右走
            }
            flag = !flag;
            appendElem(mat, list, row1, col1, row2, col2, flag);
        }
        int i = 0;
        int[] res = new int[list.size()];
        Iterator<Integer> iterator = list.iterator();
        while(iterator.hasNext()){
            res[i++] = iterator.next();
        }
        return res;
    }
    
    private void appendElem(int[][] mat, List<Integer> list, int r1, int c1, int r2, int c2, boolean startFromUp) {
        if(startFromUp){
            // 从右上方往左下方
            while(r1 <= r2){
                list.add(mat[r1++][c1--]);
            }
        }else{
            // 从左下方往右上方
            while(c2 <= c1){
                list.add(mat[r2--][c2++]);
            }
        }
    }
}

复杂度分析

两个指针一个溜了上边界和右边界，另一个溜了左边界和下边界，因此时间复杂度为O(n+m)。而整个流程中每个元素只经过了一次，时间复杂度为O(n*m)，即为整个算法的时间复杂度。
发表于 2021-12-16 13:19:49 回复(0)
提交观点

问题信息

数组 模拟
难度：
4条回答 1984浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号