Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
71 lines (64 sloc) 1.55 KB
/*
* @lc app=leetcode.cn id=498 lang=cpp
*
* [498] 对角线遍历
*
* https://leetcode-cn.com/problems/diagonal-traverse/description/
*
* algorithms
* Medium (36.29%)
* Total Accepted: 2.8K
* Total Submissions: 7.6K
* Testcase Example: '[[1,2,3],[4,5,6],[7,8,9]]'
*
* 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。
*
*
*
* 示例:
*
* 输入:
* [
* ⁠[ 1, 2, 3 ],
* ⁠[ 4, 5, 6 ],
* ⁠[ 7, 8, 9 ]
* ]
*
* 输出: [1,2,4,7,5,3,6,8,9]
*
* 解释:
*
*
*
*
*
* 说明:
*
*
* 给定矩阵中的元素总数不会超过 100000 。
*
*
*/
//iteration:对角线索引 = 对角线坐标和;根据对角线index奇偶i,swap坐标;越界跳出
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
if(matrix.empty()) return {};
const int N = matrix.size();
const int M = matrix[0].size();
vector<int> res;
for(int s = 0; s <= N + M - 2; ++s)
{
// for all i + j = s
for(int x = 0; x <= s; ++x)
{
int i = x;
int j = s - i;
if(s % 2 == 0) swap(i, j);//5.inner loop每次都是(0,s)开始的,但是偶数对角线是(s,0)开始的,所以要交换
if(i >= N || j >= M) continue;
res.push_back(matrix[i][j]);
}
}
return res;
}
};
You can’t perform that action at this time.