本文主要是介绍leetcode1329--将矩阵按对角线排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1. 题意
对角线排序
2. 题解
2.1 直接模拟
跟螺旋输出数组实际上有点像,这里需要枚举对角线数组的起始值。
class Solution {
public:void sort_dia(int br, int bc, vector<vector<int>> &mat) {vector<int> tmp;int r = mat.size();int c = mat[0].size();int cr = br;int cc = bc; while ( cr < r && cc < c) {tmp.emplace_back( mat[cr][cc] );cr++,cc++;}sort(tmp.begin(), tmp.end());cr = br, cc = bc;int idx = 0;while ( cr < r && cc < c ) {mat[cr][cc] = tmp[idx];cr++,cc++,idx++;}}vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {int r = mat.size();int c = mat[0].size();vector<vector<int>> ans;int cr = r - 1;int cc = 0;while ( cc < c) {if (cr) {sort_dia(cr, cc, mat);cr--;continue;}sort_dia(cr, cc, mat);cc++;}return vector<vector<int>>(mat);}
};
2.2 模拟+确定其实位置关系
同一对角线的位置
i − j = k i-j=k i−j=k, k k k为一定值。
所以我们只需要枚举 k k k即可。
class Solution {
public:vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {int r = mat.size();int c = mat[0].size();int br;int bc;vector<int> tmp(max(r,c), 0);// k = br - bc // for ( int k = 1 - c; k < r; ++k) {k >= 0 ? br = k : br = 0;bc = br - k ;int len = min(r - br, c - bc);for (int i = br; i < br + len;++i) {tmp[i - br] = mat[i][i - k];}sort(tmp.begin(), tmp.begin() + len);for (int i = br;i < br + len; ++i) {mat[i][ i - k ] = tmp[i - br];}}return vector<vector<int>>(mat);}
};
3. 参考
0x3f
这篇关于leetcode1329--将矩阵按对角线排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!