前往
大廳
主題

[LeetCode] 1424. Diagonal Travere II O(m*n)

テリ君(福佬模式) | 2023-11-22 20:16:56 | 巴幣 2 | 人氣 123

概念很好懂,不過要code他就挺麻煩的
一開始打了一個比較慢的
而且其實效率有點差

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

後來做了這個deque的版本就快多了
也不會那麼複雜
宣告的數值也不會那麼多

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

挺不簡單ㄉ

創作回應

相關創作

更多創作