python3 解法, 执行用时: 34 ms, 内存消耗: 16.8 MB, 提交时间: 2024-04-29 09:27:08

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        for k in range(1 - n, m):  # k = i - j
            left_i, right_i = max(k, 0), min(k + n, m)
            a = sorted(mat[i][i - k] for i in range(left_i, right_i))
            for i in range(left_i, right_i):
                mat[i][i - k] = a[i - left_i]
        return mat

javascript 解法, 执行用时: 71 ms, 内存消耗: 52 MB, 提交时间: 2024-04-29 09:26:50

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var diagonalSort = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    for (let k = 1 - n; k < m; k++) { // k = i - j
        const left_i = Math.max(k, 0);
        const right_i = Math.min(k + n, m);
        const a = [];
        for (let i = left_i; i < right_i; i++) {
            a.push(mat[i][i - k]);
        }
        a.sort((a, b) => a - b);
        for (let i = left_i; i < right_i; i++) {
            mat[i][i - k] = a[i - left_i];
        }
    }
    return mat;
};

rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-04-29 09:26:28

impl Solution {
    pub fn diagonal_sort(mut mat: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let m = mat.len() as i32;
        let n = mat[0].len() as i32;
        let mut a = vec![0; m.min(n) as usize];
        for k in 1 - n..m { // k = i - j
            let left_i = k.max(0) as usize;
            let right_i = (k + n).min(m) as usize;
            for i in left_i..right_i {
                a[i - left_i] = mat[i][(i as i32 - k) as usize];
            }
            a[..right_i - left_i].sort_unstable();
            for i in left_i..right_i {
                mat[i][(i as i32 - k) as usize] = a[i - left_i];
            }
        }
        mat
    }
}

golang 解法, 执行用时: 3 ms, 内存消耗: 3.9 MB, 提交时间: 2024-04-29 09:26:14

func diagonalSort(mat [][]int) [][]int {
    m, n := len(mat), len(mat[0])
    arr := make([]int, min(m, n))
    for k := 1 - n; k < m; k++ { // k = i - j
        a := arr[:0]
        minI := max(k, 0)
        maxI := min(k+n, m)
        for i := minI; i < maxI; i++ {
            a = append(a, mat[i][i-k])
        }
        slices.Sort(a)
        for i := minI; i < maxI; i++ {
            mat[i][i-k] = a[i-minI]
        }
    }
    return mat
}

golang 解法, 执行用时: 5 ms, 内存消耗: 4 MB, 提交时间: 2024-04-29 09:26:02

// 原地排序
type diagonalSorter struct {
    mat [][]int
    k   int
}

func (s diagonalSorter) Len() int {
    m, n := len(s.mat), len(s.mat[0])
    return min(s.k+n, m) - max(s.k, 0)
}

func (s diagonalSorter) Less(i, j int) bool {
    minI := max(s.k, 0)
    x := s.mat[minI+i][minI+i-s.k]
    y := s.mat[minI+j][minI+j-s.k]
    return x < y
}

func (s diagonalSorter) Swap(i, j int) {
    minI := max(s.k, 0)
    p := &s.mat[minI+i][minI+i-s.k]
    q := &s.mat[minI+j][minI+j-s.k]
    *p, *q = *q, *p
}

func diagonalSort(mat [][]int) [][]int {
    m, n := len(mat), len(mat[0])
    ds := diagonalSorter{mat: mat}
    for ds.k = 1 - n; ds.k < m; ds.k++ {
        sort.Sort(ds)
    }
    return mat
}

python3 解法, 执行用时: 40 ms, 内存消耗: 15.2 MB, 提交时间: 2022-11-15 11:09:45

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        for j in range(n):
            cnt = m if m < n - j else n - j
            lst = sorted([mat[x][j + x] for x in range(cnt)])
            for x in range(cnt):
                mat[x][j + x] = lst[x]

        for i in range(1, m):
            cnt = m - i if m - i < n else n
            lst = sorted([mat[i + x][x] for x in range(cnt)])
            for x in range(cnt):
                mat[i + x][x] = lst[x]
        return mat

java 解法, 执行用时: 5 ms, 内存消耗: 42.6 MB, 提交时间: 2022-11-15 11:03:37

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        // n： 矩阵行 m ：矩阵列
        int n = mat.length, m = mat[0].length;
        for (int k = 0; k < Math.min(m,n) - 1; k++) {
            // 冒泡排序
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < m - 1; j++) {
                    if (mat[i][j] > mat[i + 1][j + 1]) {
                        int t = mat[i][j];
                        mat[i][j] = mat[i + 1][j + 1];
                        mat[i + 1][j + 1] = t;
                    }
                }
            }
        }
        return mat;
    }
}