概念很好懂，不過要code他就挺麻煩的
一開始打了一個(gè)比較慢的
而且其實(shí)效率有點(diǎn)差
| class slowerSolution: def findDiagonalOrder(self, nums): m = len(nums) maxSum, size, index = 0, 0, 0 # size represents total elements in the matrix # maxSum represents -> len(nums) * 2 - 1 # index leads the position of res map = [[] for _ in range(100001)] # problem limit # get the matrix into the map for i in range(m): size += len(nums[i]) for j in range(len(nums[i])): # nums[i] numbers of elements in each rows _sum = i + j map[_sum].append(nums[i][j]) maxSum = max(maxSum, _sum) # get maxSum = len(nums) * 2 - 1 res = [0] * size # get result for i in range(maxSum + 1): # run = len(nums) * 2 - 1 times cur = map[i] # cur represents for j in range(len(cur) - 1, -1, -1): res[index] = cur[j] index += 1 return res |
後來做了這個(gè)deque的版本就快多了
也不會(huì)那麼複雜
宣告的數(shù)值也不會(huì)那麼多
| from collections import deque class Solution: def findDiagonalOrder(self, nums): queue = deque([(0,0)]) # the starting point of traversal in `nums` n = len(nums) res = [] while queue: # until queue is empty i, j = queue.popleft() # get position res.append(nums[i][j]) # col first if j == 0 and i + 1 < n: # namely queue.append([i+1, j]) # row second if j + 1 < len(nums[i]): # namely queue.append([i, j + 1]) # run until there's no queue return res |
挺不簡單ㄉ
