今日学习记录
1. 按对角线进行矩阵排序leetcode.3446
关键词：矩阵 排序
问题分析：
- 就是把对角线元素排序,但是这个对角线是左上向右下斜的
核心思路
- 就是模拟找规律,首先我们要找到对角线的规律,之前常规的对角线是 i+j 等于定值,但这个有所不同,可以发现在中间对角线上,i-j=0,在上对角中(0,1),(1,2),1-0=2-1,故 i-j 为定值;
- 故设 k = i-j+n,右上角为 k = 0-(n-1)+n = 1;对吧,左下角为 k = n+m-1;
- 根据 k,我们只用知道 i 或 j 就可以知道坐标,所以要找到排序的数组范围,只需要找 j 或 i 的最大值或者最小值,在遍历收集元素排序,还原就行
**最终代码： 注意,给出的是矩形的题解,如果是正方形 m=n;
vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
int m = grid.size(),n = grid[0].size();
for(int k = 1;k<n+m;k++){
int min_j = max(n-k,0);
int max_j = min(m-k+n-1,n-1);
vector<int> arr;
for(int j = min_j;j<=max_j;j++){
arr.push_back(grid[k+j-n][j]);
}
if(min_j>0) ranges::sort(arr);
else ranges::sort(arr,greater<int>());
for(int j = min_j;j<=max_j;j++){
grid[k+j-n][j] = arr[j-min_j];
}
}
return grid;
}