Leetcode 498:对角线遍历 Diagonal Traverse

栏目: 编程工具 · 发布时间: 4年前

内容简介:给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

对角线遍历

给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

示例:

输入:
[
[ 1, 2, 3
],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,4,7,5,3,6,8,9]

解释:

Leetcode 498:对角线遍历 Diagonal Traverse

说明:

  1. 给定矩阵中的元素总数不会超过 100000 。

思路:

实例输入的二维数组范围均是0~2

先观察一下遍历规律:(0,0)->(0,1)->(1,0)->(2,0)->(1,1)->(0,2)->(1,2)->(2,1)->(2,2)

数组索引(m,n),两种改变方式1、(m-1,n+1) 2、(m+1,n-1)

数组从(0,0)开始,先是(m-1,n+1) ,(0,0)->(-1,1)此时m=-1,超出范围,m赋值0。然后切换索引改变方式(m+1,n-1),执行两次(0,1)->(1,0)->(2,-1),n赋值0得到(2,0),再次切换为索引改变方式(m-1,n+1)直到下次超出范围(2,0)->(1,1)->(0,2)->(-1,3)。此时m<0且n>2均超出范围,(m+2,n-1),应当优先判断n是否超出范围,执行(m+2,n-1)->(1,2),避免因为m<0再次切换一次索引改变方式。然后正常切换后:(1,2)->(2,1)->(3,0),因为m>2,切换方式并(m-1,n+2)

java:

class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix.length==0||matrix[0].length==0)return new int[0];
int col=matrix.length,row=matrix[0].length;
int nums=col*row,m=0,n=0;
int res[]=new int[nums];
boolean flag=true;

for(int i=0;i<nums;i++){
res[i]=matrix[m][n];
if(flag){
n+=1; m-=1;
}else{
n-=1; m+=1;
}
if(m>=col){
m-=1; n+=2; flag=true;
}else if(n>=row){
n-=1; m+=2; flag=false;
}
if(m<0){
m=0; flag=false;
}else if(n<0){
n=0; flag=true;
}
}
return res;
}
}

注意点:

if (matrix.length==0||matrix[0].length==0)return new int[0]; 首先判断是否为空数组,另外  matrix.length==0||matrix[0].length==0 判断条件顺序不能颠倒,因为如果  matrix.length==0 后面的  matrix[0].length==0 不会再判断,即返回空数组;但是 matrix[0].length==0 在前时,如果输入数组为空, matrix[0] 会报错因为matrix并没有0号索引。

for循环里应当先判断m、n是否大于或等于各自的最大长度,然后执行(m-1,n+2)、(m+2,n-1)。避免出现m、n同时小于0时flag布尔值转换两次的错误。

python:

class Solution:
def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
if(len(matrix)==0 or len(matrix[0])==0):
return []
col=len(matrix)
row=len(matrix[0])
nums=col*row
m=n=0
flag=True
res=[]
for i in range(nums):
res.append(matrix[m][n])
if flag:
m-=1
n+=1
else:
m+=1
n-=1
if m>=col:
m-=1
n+=2
flag=True
elif n>=row:
m+=2
n-=1
flag=False
if m<0:
m=0
flag=False
elif n<0:
n=0
flag=True
return res

Leetcode 498:对角线遍历 Diagonal Traverse


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C语言基础

C语言基础

安博教育集团 / 2012-2 / 37.00元

《C语言基础》深入浅出地介绍了C语言程序设计的基础知识,内容涉及C语言基础、算法基础、变量、数据类型、运算符、输入/输出相关函数、选择结构、循环结构、各种表达式、数组、字符串、指针、函数、结构体、ISO C99的扩展语法等。全书内容丰富,结构严谨,层次清晰,语言生动,论述精准而深刻,实例丰富而实用。 《C语言基础》不仅适合用做计算机职业培训的首选教材,也可作为普通高校教材使用,更是C语言初学......一起来看看 《C语言基础》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具