ETH官方钱包

前往
大廳
主題

LeetCode - 2679. Sum in a Matrix 解題心得

Not In My Back Yard | 2024-07-17 12:00:04 | 巴幣 2 | 人氣 66

題目連結:


題目意譯:
你被給定一個索引值從 0 開始數的二維整數矩陣 nums。一開始你的分數為 0。執行以下操作直到矩陣變為空為止:
    1. 從矩陣中的每一列,選出其中最大的數字並移除。如果有多個最大,選擇任意一個無關緊要。
    2. 從第 1 步移除的數字中找出最大者並將該值加到你的分數中。

回傳最終分數。

限制:
1 ≦ nums.length ≦ 300
1 ≦ nums[i].length ≦ 500
0 ≦ nums[i][j] ≦ 10 ^ 3



範例測資:
範例 1:
輸入: nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]
輸出: 15
解釋: 在第一次操作,我們移除 7 、 6 、 6 和 3。我們接著將 7 加到我們的分數;接著我們移除 2 、 4 、 5 和 2。我們將 5 加到我們的分數中。最後我們移除 1 、 2 、 3 和 1。我們將 3 加到我們的分數裡。因此我們的最終分數為  7 + 5 + 3 = 15。

範例 2:
輸入: nums = [[1]]
輸出: 1
解釋: 我們移除 1 並將其加到答案中。我們回傳 1。


解題思維:
由於每一次都會把每一列各自的最大值移除掉,因此直接將每一列各自由小排到大(或是由大排到小)即可。

並且可以看到此時同一行的數字必定會在同一次操作被移除(因為每一列都按照數值大小排了),因此此時掃過每一行求最大值,然後把每一行的結果加總即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作