首页 > 试题广场 >

对角线遍历矩阵

[编程题]对角线遍历矩阵

热度指数：1209 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个大小为 n*m 的矩阵，请以对角线遍历并返回遍历结果

数据范围： $1 \le n,m \le 10000 \$ ，矩阵中的元素满足 $1 \le val \le 10^5 \$

示例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

pein531

双指针流程

指定两个指针p₁和p₂从mat[0][0]位置出发，两个指针同步移动，不存在一个走另一个不走的情况：

p₁一直往右走，直到碰到右边界就往下走；
p₂一直往下走，直到碰到左边界就往右走。

两个指针每次移动都能确定矩阵的一条对角斜线，根据操作的奇偶性，每次按照从右上到左下或从左下到右上将矩阵元素追加到链表中即可。

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)

Python3

liangzhengjie

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param mat int整型二维数组
# @return int整型一维数组
#
class Solution:
    def diagonalOrder(self, mat: List[List[int]]) -> List[int]:
        # write code here
        if len(mat) == 0:
            return []
        up_and_right = 1
        x = 0
        y = 0
        res = []
        while not (x == len(mat) - 1 and y == len(mat[0]) - 1):
            res.append(mat[x][y])
            if up_and_right:
                if x - 1 = len(mat[0]):
                    up_and_right = False
                    # 右上部分顺时针寻找
                    if y + 1 < len(mat[0]):
                        y += 1
                        continue
                    if x + 1 < len(mat):
                        x += 1
                        continue
                else:
                    x -= 1
                    y += 1
            else:
                if x + 1 >= len(mat) or y - 1 < 0:
                    up_and_right = True
                    # 左下部分逆时针寻找
                    if x + 1 < len(mat):
                        x += 1
                        continue
                    if y + 1 < len(mat[0]):
                        y += 1
                        continue
                else:
                    x += 1
                    y -= 1
        res.append(mat[x][y])
        return res

发表于 2024-04-27 00:33:16 回复(0)

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param mat int整型二维数组 
 * @return int整型一维数组
*/
func diagonalOrder( mat [][]int ) []int {
    n,m:=len(mat),len(mat[0])
    ans:=make([][]int,n+m-1)
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            k:=i+j
            if ans[k]==nil{
                ans[k]=[]int{}
            }
            if k%2!=0{
                ans[k]=append(ans[k],mat[i][j])
            }else{
                ans[k]=append([]int{mat[i][j]},ans[k]...)
            }
        }
    }
    res:=[]int{}
    for _,arr:=range ans{
        res=append(res,arr...)
    }
    return res
}

发表于 2023-03-10 20:49:42 回复(0)

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)

饥饿的懒羊羊在刷题

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param mat int整型二维数组
* @return int整型一维数组
*/
public int[] diagonalOrder (int[][] mat) {
// write code here
int i = 0,k=0;
int m=mat.length,n=mat[0].length;
int []arr=new int[m*n];

// i代表x+y,即要走的趟数，总共要走m+n-1=5趟，i最大为4
while (i<m+n-1){
// x1的初始值
int x1 = i<m ? i : m-1;
int y1 = i-x1;
while (x1>=0 && y1<=n-1){
arr[k++] = mat[x1][y1];
x1--;
y1++;
}
i++;
if(i==m+n-1){
break;
}

int y2 = i<n ? i : n-1;
int x2= i-y2;
while (x2<=m-1 && y2>=0){
arr[k++] = mat[x2][y2];
x2++;
y2--;
}
i++;
}
return arr;
}

}

发表于 2022-05-10 21:50:09 回复(0)

Java

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)

C++

LQstoic

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param mat int整型vector<vector<>>
     * @return int整型vector
     */
    vector<int> diagonalOrder(vector<vector<int> >& mat) {
        // write code here
        int row=mat.size();
        int col=mat[0].size();
        vector<int>ans;
        for(int i=0;i<=row+col-2;i++)
        {
            int m;
            if(i%2)//奇数
            {

                for(m=0;m<=i && m<row;m++)
               {
                   if(i-m<col)
                   {
                      ans.push_back(mat[m][i-m]);
                   }
               }
            }
            else
            {

               for(m=0;m<=i && m<col;m++)
               {
                   if(i-m<row)
                   {
                      ans.push_back(mat[i-m][m]);
                   }
               }
            }
        }
        return ans;

    }
};

发表于 2021-11-19 16:09:58 回复(0)