[每日一题] 1329.将矩阵按对角线排序

Richard

2024 年 04 月 29 日

133 次浏览

暂无评论

1663字数

LeetCode

> https://leetcode.cn/problems/sort-the-matrix-diagonally/description/?envType=daily-question&envId=2024-04-11

对角线排序，练习实现排序算法罢了。注意矩阵最大为 $100 \times 100$ ，用 $O(n^2)$ 的排序算法会超时。

当然这题也可以将对角元素取出来用 `std::sort` 进行排序，这里只是练习一下手写排序算法。

```c++
class Solution {
public:
    std::vector<std::vector<int>> diagonalSort(std::vector<std::vector<int>>& mat) {
        const int rows = mat.size(), cols = mat[0].size();

std::function<void(const int &, const int &, const int &)> quickSort = [&] (const int &rowBegin, const int &colBegin, const int &endOffset) {
            if (rowBegin < 0 || rowBegin >= rows || colBegin < 0 || colBegin >= cols || endOffset <= 0)
                return;

if (endOffset == 1) {
                if (mat[rowBegin][colBegin] > mat[rowBegin + 1][colBegin + 1])
                    std::swap(mat[rowBegin][colBegin], mat[rowBegin + 1][colBegin + 1]);
                return;
            }

int baseline;
            int &a = mat[rowBegin][colBegin], &c = mat[rowBegin + endOffset][colBegin + endOffset];
            int &b = mat[rowBegin + endOffset / 2][colBegin + endOffset / 2];
            if ((a < b && b < c) || (c < b && b < a)) {
                baseline = b;
                std::swap(a, b);
            } else if ((b < a && a < c) || (c < a && a < b)) {
                baseline = a;
            } else {
                baseline = c;
                std::swap(a, c);
            }

std::pair<int, int> left = {rowBegin, colBegin}, right = {rowBegin + endOffset, colBegin + endOffset};
            while (left.first < right.first) {
                while (left.first < right.first && mat[right.first][right.second] >= baseline)
                    --right.first, --right.second;

while (left.first < right.first && mat[left.first][left.second] <= baseline)
                    ++left.first, ++left.second;

if (left.first != right.first)
                    std::swap(mat[left.first][left.second], mat[right.first][right.second]);
            }
            std::swap(mat[rowBegin][colBegin], mat[right.first][right.second]);

quickSort(rowBegin, colBegin, right.first - rowBegin - 1);
            quickSort(right.first + 1, right.second + 1, endOffset - right.first + rowBegin - 1);
        };

quickSort(0, 0, std::min(rows, cols) - 1);
        for (int i = 1; i < rows; ++i)
            quickSort(i, 0, std::min(rows - i, cols) - 1);
        for (int i = 1; i < cols; ++i)
            quickSort(0, i, std::min(rows, cols - i) - 1);

return mat;
    }
};
```

- 时间复杂度 $O(mn \cdot logmn)$ ，其中 $mn$ 为矩阵的大小。
- 空间复杂度 $O(1)$ ，除了输出不需要额外的辅助空间。

最后修改：2024 年 05 月 06 日