498. 对角线遍历-遍历矩阵

89 阅读 0 评论 59 点赞

我是靠谱客的博主灵巧唇彩，这篇文章主要介绍498. 对角线遍历-遍历矩阵，现在分享给大家，希望可以做个参考。

498. 对角线遍历-遍历矩阵

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

遍历之后，我们在做一个反序工作解题代码如下：

复制代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findDiagonalOrder(int** mat, int matSize, int* matColSize, int* returnSize){
    int n=matSize,m=matColSize[0];
    int *re=(int *)malloc(sizeof(int)*(n*m+n+m));
    int size=0;
    int x=0,y=0;
    int  direction=0;
    while(true){
        if(y!=m){
           
            int index_x=x,index_y=y;
             y++;
              re[size++]=mat[index_x][index_y];

while(index_x+1<n&&index_y-1>=0){
                 index_x++;
                 
                 index_y--;
                 re[size++]=mat[index_x][index_y];

}
        }
        else{
            
              x++;
              if(x>=n){
                  break;
              }
             int index_x=x,index_y=y-1;
               re[size++]=mat[index_x][index_y];

while(index_x+1<n&&index_y-1>=0){
                 index_x++;
                 
                 index_y--;
                 re[size++]=mat[index_x][index_y];

}

}
      
        if(direction%2==0){
            re[size++]=-10000;
        }
        else{
             re[size++]=-20000;

}
        direction++;
   
    }
  
    for(int i=0;i<size;i++){
        if(re[i]==-20000){
            int j=i;
            while(re[j]!=-10000&&j!=size){
                j++;
            }
            for(int k=0;k<(j-i-1)/2;k++){
                int t=re[i+1+k];
                re[i+1+k]=re[j-1-k];
                re[j-1-k]=t;

}

}
    }
    int resize=0;
      for(int i=0;i<size;i++){
          if(re[i]!=-10000&&re[i]!=-20000){
              re[resize++]=re[i];
          }

}

*returnSize=resize;
    return re;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findDiagonalOrder(int** mat, int matSize, int* matColSize, int* returnSize){
    int n=matSize,m=matColSize[0];
    int *re=(int *)malloc(sizeof(int)*(n*m+n+m));
    int size=0;
    int x=0,y=0;
    int  direction=0;
    while(true){
        if(y!=m){
           
            int index_x=x,index_y=y;
             y++;
              re[size++]=mat[index_x][index_y];

             while(index_x+1<n&&index_y-1>=0){
                 index_x++;
                 
                 index_y--;
                 re[size++]=mat[index_x][index_y];

             }
        }
        else{
            
              x++;
              if(x>=n){
                  break;
              }
             int index_x=x,index_y=y-1;
               re[size++]=mat[index_x][index_y];

             while(index_x+1<n&&index_y-1>=0){
                 index_x++;
                 
                 index_y--;
                 re[size++]=mat[index_x][index_y];

             }
           

        }
      
        if(direction%2==0){
            re[size++]=-10000;
        }
        else{
             re[size++]=-20000;

        }
        direction++;
   
    }
  
    for(int i=0;i<size;i++){
        if(re[i]==-20000){
            int j=i;
            while(re[j]!=-10000&&j!=size){
                j++;
            }
            for(int k=0;k<(j-i-1)/2;k++){
                int t=re[i+1+k];
                re[i+1+k]=re[j-1-k];
                re[j-1-k]=t;

            }

        }
    }
    int resize=0;
      for(int i=0;i<size;i++){
          if(re[i]!=-10000&&re[i]!=-20000){
              re[resize++]=re[i];
          }

      }



 
  *returnSize=resize;
    return re;

}