java 解法, 执行用时: 114 ms, 内存消耗: 65.1 MB, 提交时间: 2023-09-25 17:37:08

class Solution {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        int len = 0;
		Map<Integer,List<Integer>> map = new TreeMap<>();
		for(int i = 0;i < nums.size();i++) {
			len += nums.get(i).size(); // 获取最后要返回的数组的长度，即元素个数
			for(int j = 0;j < nums.get(i).size();j++) {
				if(map.containsKey(i + j)) {
					map.get(i + j).add(nums.get(i).get(j));
				}
				else {
					List<Integer> list = new ArrayList<>();
					list.add(nums.get(i).get(j));
					map.put(i + j, list);
				}
			}
		}
		int[] ans = new int[len];
		int index = 0;
		for(int key : map.keySet()) { // 遍历map
			List<Integer> list = map.get(key);
			for(int j = list.size() - 1;j >= 0;j--) { // 根据题目的输出要求确定生成数组中元素的顺序
				ans[index] = list.get(j);
				index++;
			}
		}
        return ans;
    }
}

rust 解法, 执行用时: 44 ms, 内存消耗: 8.7 MB, 提交时间: 2023-09-25 17:35:59

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn find_diagonal_order(nums: Vec<Vec<i32>>) -> Vec<i32> {
        let mut res = vec![];
        let mut heap = BinaryHeap::new();
        heap.push((Reverse(0), 0, 0));
        let mut used = vec![];
        for i in 0..nums.len() {
            used.push(vec![false; nums[i].len()]);
        }

        while !heap.is_empty() {
            let item = heap.pop().unwrap();
            res.push(nums[item.1][item.2]);

            // 将右边的数加入到堆中
            if item.2 + 1 < nums[item.1].len() && !used[item.1][item.2+1] {
                heap.push((Reverse(item.1 + item.2+1), item.1, item.2+1));
                used[item.1][item.2+1] = true;
            }

            // 将下边的数加入到堆中
            if item.1 + 1 < nums.len() && item.2 < nums[item.1 + 1].len() && !used[item.1+1][item.2] {
                heap.push((Reverse(item.1 + item.2+1), item.1+1, item.2));
                used[item.1+1][item.2] = true;
            }
        }
        res
    }
}

golang 解法, 执行用时: 160 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-25 17:35:05

func findDiagonalOrder(nums [][]int) []int {
    
    var (
        indexes = make([][2]int, 0)
    )
    for x, row := range nums{
        for y, _ := range row{
            indexes = append(indexes, [2]int{x, y})
        }
    }

    sort.Slice(indexes, func(i, j int)bool{
        a, b := indexes[i], indexes[j]
        suma, sumb := a[0] + a[1], b[0] + b[1]
        return suma < sumb || suma == sumb && a[1] < b[1]
    })

    var ans = make([]int, 0, len(indexes))
    for _, item := range indexes{
        ans = append(ans, nums[item[0]][item[1]])
    }

    return ans
}

python3 解法, 执行用时: 200 ms, 内存消耗: 43.8 MB, 提交时间: 2023-09-25 17:34:40

# 对下标排序
class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        indexes = [(x, y) for x, rows in enumerate(nums) for y in range(len(rows)) ]
        indexes.sort(key = lambda item: (sum(item), item[1]))

        return [nums[x][y] for x, y in indexes]

php 解法, 执行用时: 308 ms, 内存消耗: 92.9 MB, 提交时间: 2023-09-25 17:33:13

class Solution {

    /**
     * @param Integer[][] $nums
     * @return Integer[]
     */
    function findDiagonalOrder($nums) {
        $map = [];
        $array = [];
        for($i = 0;$i< count($nums);$i++){
            for($j=0;$j< count($nums[$i]);$j++){
                $map[$i+$j][] = $nums[$i][$j];
            }
        }

        foreach ($map as $item){
            for($i = count($item)-1;$i >= 0;$i--){
                $array[] = $item[$i];
            }
        }
        return $array;
    }
}

python3 解法, 执行用时: 220 ms, 内存消耗: 34.7 MB, 提交时间: 2023-09-25 17:32:22

# nums[i][j] 必然在第（i + j）条斜线的结果中。i 越小，结果越靠后。
class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        sub_result = []
        for i in range(len(nums)):
            for j in range(len(nums[i])):
                if i + j >= len(sub_result):
                    sub_result.append([])
                sub_result[i + j].append(nums[i][j])
                
        result = []
        for sub in sub_result:
            result += sub[::-1]
        return result