498_Diagonal-Traverse
2024-09-14 20:37:28
498_Diagonal-Traverse
目录
Description
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.
Example:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,4,7,5,3,6,8,9]
Explanation:
Note:
- The total number of elements of the given matrix will not exceed 10,000.
Solution
Java solution
class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return new int[0];
}
int m = matrix.length, n = matrix[0].length;
int[] res = new int[m * n];
int row = 0, col = 0, d = 1;
for (int i = 0; i < m*n; i++) {
res[i] = matrix[row][col];
row -= d;
col += d;
// lower border
if (row >= m) {
row -= 1;
col += 2;
d = -d;
}
// right border
if (col >= n) {
col -= 1;
row += 2;
d = -d;
}
// upper border
if (row < 0) {
row = 0;
d = -d;
}
// left border
if (col < 0) {
col = 0;
d = -d;
}
}
return res;
}
}
Runtime: 7 ms. Your runtime beats 97.45 % of java submissions.
Python solution 1
class Solution:
def findDiagonalOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if matrix == []:
return []
m, n = len(matrix), len(matrix[0])
coordinates = [(i, j) for i in range(m) for j in range(n)]
coordinates.sort(key=lambda x: sum(x) * max(m, n) - x[sum(x) % 2])
return [matrix[x][y] for x, y in coordinates]
Runtime: 164 ms. Your runtime beats 37.74 % of python3 submissions.
Python solution 2
class Solution:
def findDiagonalOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
entries = [(i + j, (j, i)[(i ^ j) & 1], val)
for i, row in enumerate(matrix)
for j, val in enumerate(row)]
return [e[2] for e in sorted(entries)]
Runtime: 136 ms. Your runtime beats 77.36 % of python3 submissions.
Python solution 3
class Solution:
def findDiagonalOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
m, n = len(matrix), len(matrix and matrix[0])
return [matrix[i][d-i]
for d in range(m+n-1)
for i in range(max(0, d-n+1), min(d+1, m))[::d%2*2-1]]
Runtime: 148 ms. Your runtime beats 59.43 % of python3 submissions.
最新文章
- Linux教程:Bash技巧,让chmod只修改某个目录下文件夹或者文件的权限
- Octave安装和使用
- js随机颜色生成
- Spring+Mybatis多数据源配置
- Mac地址绑定的wifi
- C#：文件、文件夹特别操作
- git 冲突解决（转载）
- 【转载】linux中互斥尽量用mutex，不用semaphore
- Ubuntu 创建快捷方式的方法
- HTML资源（推荐）
- marked插件在线实时解析markdown的web小工具
- Gson序列化对象如何忽略字段
- SQLServer中PRECISION和LENGTH,还有SCALE的区别
- git工具——版本的创建与回退
- 数据仓库中的Inmon与Kimball架构
- 学习ActiveMQ(六)：JMS消息的确认与重发机制
- VB VB 定义及区别
- 19.职责链模式（Chain of Responsibility Pattern）
- 关于SLG的产品市场判断
- outlook关闭时最小化工具