求问今天的daily challenge， 为啥我的TLE???

LEETCODE Code1424. Diagonal Traverse II


这题其实不难，主要是要知道colIndex+rowIndex = constant. 但是楼主首先，loop over first col, then loop last col.  time complexity should be O(N) 因为每个element只访问一遍。我看答案是用hashmap。但是我感觉总的tc应该是一样的。为啥我的过不了？？转码选手轻喷，抱着学习的心态发帖。。。。




class Solution {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        List<Integer> ans = new ArrayList<>();
        int m = nums.size();
        int maxCol = 0;
        for (int i = 0; i<m; i++) {
            int indexSum = i;
            maxCol = Math.max(maxCol, nums.get(i).size());
            for (int row = i; row >= 0; row--) {
                int col = indexSum - row;
                if (col<nums.get(row).size()) {
                    ans.add(nums.get(row).get(col));
                }
            }
        }
        for (int j = 1; j<maxCol; j++) {
            int indexSum = m-1+j;
            for (int row = m-1; row>=0; row--) {
                int col = indexSum - row;
                if (col < nums.get(row).size()) {
                    ans.add(nums.get(row).get(col));
                }
            }
        }
        int size = ans.size();
        int[] res = new int[size];
        for (int i = 0; i<size; i++) {
            res[i] = ans.get(i);
        }
   
        return res;
    }
}

maxCol 可以很大。所以会tle

你可以看看solution里的bfs解法

mc2 发表于 2023-11-22 13:57
maxCol 可以很大。所以会tle

你可以看看solution里的bfs解法

这不就是周赛大神吗。欢迎大神莅临指导。

1. def findDiagonalOrder(self, grid):
   
2.      m = len(grid)
   
3.      n = max(len(r) for r in grid)
   
4.      ans = [[] for _ in range(m+n)]
   
5.      for i in range(len(grid)):
   
6.           for j in range(len(grid[i])):
   
7.                ans[i+j].append(grid[i][j])
   
8.     return [r[i] for r in ans for i in range(len(r)-1, -1, -1)]

复制代码