Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.
Example 1:
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]] Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 1001 <= mat[i][j] <= 100
Solution: HashTable
Collect each diagonal’s (keyed by i – j) elements into an array and sort it separately.
If we offset the key by n, e.g. i – j + n, we can use an array instead of a hashtable.
Time complexity: O(m*n + (m+n) * (m+n) * log(m + n))) = (n^2*logn)
Space complexity: O(m*n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: vector<vector<int>> diagonalSort(vector<vector<int>>& mat) { const int m = mat.size(); const int n = mat[0].size(); vector<deque<int>> qs(m + n); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) qs[i - j + n].push_back(mat[i][j]); for (auto& q : qs) sort(begin(q), end(q)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { mat[i][j] = qs[i - j + n].front(); qs[i - j + n].pop_front(); } return mat; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment