[leetcode题解]1329. Sort the Matrix Diagonally(将矩阵按对角线排序)

题目的意思比较明确,题目的输入是一个二维矩阵,行为m列为n。

题目的要求是对于该矩阵,所有元素从左上角到右下角这条直线上进行排序。

最后返回排序后的矩阵即可。

解题思路:

使用c++的话因为有vector等容器,非常方便,总体思路就是找到每一个从左上角到右下角的元素,放入vector中,然后使用sort对这个vector进行快速排序,然后把排序后的元素按顺序更新到矩阵中即可。本文由iaccepted发表在凌风技术站的leetcode分类下,该分类会持续更新所有leetcode题目解析。

所以总的流程是对每个斜线取元素->排序->斜线设置元素。

代码中也是直接分三步搞定,getValues是获取当前斜行的所有元素,其值存入vector中,然后对该vector进行sort,最后通过setValues设置到mat中。

本文由iaccepted发表在”凌风技术站”的leetcode分类下,该分类会持续更新所有leetcode题目解析。

代码如下:

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        //本文由iaccepted发表在凌风技术站的leetcode分类下,该分类会持续更新所有leetcode题目解析
        int i, j;
        int rows, cols;
        vector<int> res;
        
        rows = mat.size();
        cols = mat[0].size();
        for (i = 0; i < rows; i++) {
            getValues(mat, res, i, 0);
            sort(res.begin(), res.end());
            setValues(mat, res, i, 0);
        }
        
        for (i = 0; i < cols; i++) {
            getValues(mat, res, 0, i);
            sort(res.begin(), res.end());
            setValues(mat, res, 0, i);
        }
        return mat;
    }
    
private:
    void getValues(vector<vector<int>> &mat, vector<int> &res, int x, int y) {
        int rows = mat.size();
        int cols = mat[0].size();
        
        res.clear();
        while (x < rows && y < cols) {
            res.push_back(mat[x][y]);
            ++x;
            ++y;
        }
    }
    
    void setValues(vector<vector<int>> &mat, vector<int> &res, int x, int y) {
        int size = res.size();
        int i;
        
        for (i = 0; i < size; i++) {
            mat[x][y] = res[i];
            ++x;
            ++y;
        }
    }
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]1329. Sort the Matrix Diagonally(将矩阵按对角线排序)

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/241.html

相关文章