矩阵中对角线的遍历问题【C++】

1，按对角线进行矩阵排序

题目链接：3446. 按对角线进行矩阵排序 - 力扣（LeetCode）

【题目描述】

对于一个m*n的矩阵grid，要求对该矩阵进行 变换，使得变换后的矩阵满足：

主对角线右上的所有对角线上，元素升序排列。

主对角线左下的所有对角线上，元素降序排列。

【思路】

对于一个矩阵grid，我们可以发现，从右上角到左下角的所有对角线中，同一条对角线上的元素满足：行号i减去列号j是一个定值。

令k=i-j+n，这里加n是为了避免k出现负数。

对于右上角的对角线，k=i-j+n=1。对于左下角的对角线k=m+n-1；

所以，我们可以枚举k=1,2,3,......,m+n-1；相当于从右上角开始，到左下角结束，遍历每条对角线。

 接下来需要求出每条对角线上j的取值范围，从而可以遍历对角线上的元素 。

k=i-j+n——>j=i+n-k。

当i=0时，j取最小值，j=n-k。但是j可能会出现负数，所以最小的j=max(0,n-k）。

当i=m-1时，j取最大值，j=m+n-1-k。但是j可能会超出范围，所以最大的j=min(n-1,m+n-1-k）。

对于一个矩阵，如何区别主对角线的右上和左下？？？

我们可以通过j的最小值来确定，观察上图可看出，对于主对角线右上的对角线来说，j的最小值都是大于0的，相反，对于主对角线走下的对角线来说，j的最小值都是等于0的。所以可以 以这点来做区分。

接下来就可以进行模拟了：

枚举k=1,2,3......,m+n-1；

求出每条对角线上j的范围。将该对角线上的 元素加入数组 。排序后（升序或者降序）写回原数组。

【代码】

class Solution {
public:vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {//k=i-j+n;int m=grid.size(),n=grid[0].size();//右上角k=1//左下角k=m+n-1for(int k=1;k<m+n;k++){//计算当前对角线的最小值和最大值int min_j=max(n-k,0);int max_j=min(m+n-k-1,n-1);vector<int> a;for(int j=min_j;j<=max_j;j++){a.push_back(grid[k+j-n][j]);}//主对角线右上 升序排列if(min_j>0){ranges::sort(a);}else{//主对角线左下  降序排列ranges::sort(a,greater<int>());}//写回数组for(int j=min_j;j<=max_j;j++){grid[k+j-n][j]=a[j-min_j];}}return grid;}
};

时间复杂度：O(N^2*logN)

空间复杂度：O(N) 

2，将矩阵按对角线进行排序

题目链接：1329. 将矩阵按对角线排序 - 力扣（LeetCode）

本题和上题思路一致，但是要求每条对角线都按升序排列。

class Solution {
public:vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {int m=mat.size(),n=mat[0].size();for(int k=1;k<m+n;k++){int min_j=max(n-k,0);int max_j=min(m+n-k-1,n-1);vector<int> a;for(int  j=min_j;j<=max_j;j++)a.push_back(mat[k+j-n][j]);ranges::sort(a);for(int j=min_j;j<=max_j;j++)mat[k+j-n][j]=a[j-min_j];}return mat;}
};

 3，对角线上不同值的数量差

题目链接：2711. 对角线上不同值的数量差 - 力扣（LeetCode）

【题目描述】 

对于一个大小为m*n的矩阵grid，返回一个同等规模的数组ans，其中ans[i][j]表示：

在矩阵grid中，grid[i][j]左上角对角线中不同值的数量和右下角对角线不同值的数量的差值，对最后结果再取绝对值。

【思路1】暴力计算 ：

遍历grid[i][j]的每一个元素，计算topLeft[i][j]和bottomRight[i][j]。

首先我们可以定义一个unordered_set容器，遍历元素的时候，将元素加入到该容器中。

计算topLeft[i][j]：从[i,j]位置开始，遍历左上角对角线，进行[i--,j--]操作。直到矩阵的边界。

这个过程中，把遍历到的元素加入到容器中，最终topLeft[i][j]就是容器的大小。

计算bottomRight[i][j]：从[i,j]位置开始，遍历右下角对角线，进行[i++,j++]操作。直到矩阵的边界。这个过程中，把遍历到的元素加入到容器中 ，最终bottomRight[i][j]就是容器的大小。

【思路1代码】

class Solution {
public:vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();vector<vector<int>> ans(m,vector<int>(n,0));unordered_set<int> st;//天然的去重，容器的大小就是 不同值的数量for(int i=0;i<m;i++){for(int j=0;j<n;j++){st.clear();//查找左上角 不同值的个数for(int x=i-1,y=j-1;x>=0&&y>=0;x--,y--)st.insert(grid[x][y]);int topLeft=st.size();//查找右下角 不同值的个数st.clear();for(int x=i+1,y=j+1;x<m&&y<n;x++,y++)st.insert(grid[x][y]);int bottomRight=st.size();ans[i][j]=abs(topLeft-bottomRight);}}return ans;}
};

时间复杂度：O(m*n*(min(m,n))，m和n分别为grid的行数和列数。

计算一个topLeft和bottomRight需要O(min(m,n))的时间。 

【思路2】

该方法就要使用到前面两道题对 对角线的操作思路。

思路一的方法：对于同一条对角线，会遍历多次。比如求ans[0][0]，会遍历一次主对角线，求ans[1][1]的时候，会遍历一次主对角线，求ans[1][1]也会遍历一次主对角线，所以存在多次重复遍历。

我们可以按照前面两道题的思路。

将每条对角线看成是一个一维数组d。

对于d[i]来说：

topLeft[i]是d[i]左侧不同值的数量，我们可以从左向右遍历，将元素加入到哈希集合中，直到遍历到d[i]，此时topLeft就是哈希集合的大小。

bottomRight[i]是右侧不同值的数量 ，我们可以从右向左遍历，将元素加入到哈希集合中，直到遍历到d[i]，此时bottomRight就是哈希集合的大小。

【思路2代码】

class Solution {
public:vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();unordered_set<int> st;vector<vector<int>> ans(m,vector<int>(n));//枚举k 从1到m+n-1//k=i-j+nfor(int k=1;k<m+n;k++){//求出j的范围int min_j=max(n-k,0);//i=0时，j=n-k，但不能是负数int max_j=min(m+n-k-1,n-1);//i=m-1时，j=m+n-1-k,但不能超出范围st.clear();//计算左侧不同值的数量 topLeft//从 左向右遍历for(int j=min_j;j<=max_j;j++){int i=k+j-n;ans[i][j]=st.size(); //topLeft[i][j]=st.size();st.insert(grid[i][j]);}//计算右侧最大值的数量  bottomRight//从右向左遍历st.clear();for(int j=max_j;j>=min_j;j--){int i=k+j-n;ans[i][j]=abs(ans[i][j]-(int)st.size());//st.size()返回值时size_tst.insert(grid[i][j]);}}return ans;}
};

时间复杂度：O(m*n)，每个单元格访问两次。

4，对角线遍历

题目链接：498. 对角线遍历 - 力扣（LeetCode）

 【思路】

我们前面所讲题的对角线遍历，对角线都是从左上角到右下角的一条线。都是主对角线。

而本题 方向相反，都是副对角线。我们可以将数组中的每一行进行翻转，就可以转化成主对角线了。

之后，使用前面的思想，遍历每条对角线。

k=i-j+n；枚举k，从1到m+n-1；

 求出每条对角线j的最大值和最小值。

对于每条对角线，我们可能需要从下到上遍历，也可能需要从上到下遍历。对应的j就需要从大到小遍历，也可能需要从小到大遍历。

我们可以定义一个变量flag，flag=1时从下到上遍历，也就是j从从大到小遍历。

flag=0时，从上到下遍历，也就是j从小到大遍历。

开始时，需要从下到上遍历，flag设为1.

【代码】

class Solution {
public:vector<int> findDiagonalOrder(vector<vector<int>>& mat) {int m=mat.size(),n=mat[0].size();//翻转每一行for(auto& v:mat){reverse(v.begin(),v.end());}vector<int> ans;int flag=1;//k=i-j+n//1,2,3......m+n-1//枚举k，枚举每一条对角线for(int k=1;k<m+n;k++){//求出j的最小值和最大值int min_j=max(n-k,0);int  max_j=min(m+n-k-1,n-1);//从下到上遍历  对于j是从大到小遍历if(flag){for(int j=max_j;j>=min_j;j--){int i=k+j-n;ans.push_back(mat[i][j]);}}else  //从上到下遍历  对应的j从小到大遍历{for(int  j=min_j;j<=max_j;j++){int i=k+j-n;ans.push_back(mat[i][j]);}}flag^=1;}return ans;}
};

总结：

对角线的遍历（主对角线）：对于一个m*n的矩阵。

在同一条对角线上的元素，行号i减去列号j是一个定值。k=i-j+n；

k的值从1开始到m+n-1。就是主对角线从右上角对角线开始，一直到左下角对角线。

遍历对角线时，我们只需求出j的范围即可，i=k+j-n。但需要注意j不能小于0，也不能超出数组的范围。然后就可以对这条对角线进行操作了。