[Leetcode解題] 2679. Sum in a Matrix
題目
給定一個整數矩陣 nums,初始分數為 0。重複以下操作,直到矩陣為空:
- 從每一列(row)各取出並移除一個最大值;若最大值重複,任選一個即可。
- 找出這一輪移除的所有數字中的最大值,加到分數中。
回傳最後的總分。
例如 nums = [[7, 2, 1], [6, 4, 2], [6, 5, 3], [3, 2, 1]]:三輪分別加上 7、5、3,所以答案是 15。
題目限制:列數介於 1 到 300,欄數介於 1 到 500,且 0 <= nums[i][j] <= 1000。
解題思路
1. 直接模擬會重複尋找最大值
假設矩陣有 m 列、n 欄。如果每一輪都掃描每列剩餘的元素,找出並刪除最大值,總共需要 n 輪。
單列的掃描次數為 n + (n - 1) + ... + 1,因此整體需要 $O(mn^2)$ 的時間。若使用陣列刪除元素,還可能需要搬移後面的元素。
觀察一列的取出順序:不論原本如何排列,總是先取最大值,再取第二大值,直到取完。這個順序可以透過排序一次取得。
2. 每列排序後,同一欄就是同一輪取出的數字
將每一列各自按照遞增順序排序:
原始矩陣 每列排序後
[7, 2, 1] [1, 2, 7]
[6, 4, 2] → [2, 4, 6]
[6, 5, 3] [3, 5, 6]
[3, 2, 1] [1, 2, 3]
此時:
- 最右欄是每列的最大值,對應第一輪。
- 倒數第二欄是每列的第二大值,對應第二輪。
- 最左欄是每列的最小值,對應最後一輪。
所以每一輪的得分,就是對應欄的最大值。我們不需要真的刪除元素,只需要掃描每一欄。
3. 為什麼程式可以從左往右累加?
題目實際上從最大值開始移除,對應排序後由右往左處理。但每一輪取出的數字已由排序結果決定,不會因為累加順序而改變。
最後只要求總和,而加法的順序不影響答案,因此程式可以直接由左往右,累加每一欄的最大值。
令排序後的矩陣為 a,答案可以寫成:
注意:必須先將每一列分別排序,才能讓同一欄的元素對應到同一輪。原始矩陣的欄位置並沒有這個意義。
範例推演
使用上面的矩陣,排序後依照題目操作順序,由右往左查看:
| 輪次 | 對應欄索引 | 每列移除的數字 | 本輪得分 | 累計分數 |
|---|---|---|---|---|
| 1 | 2 | [7, 6, 6, 3] |
7 | 7 |
| 2 | 1 | [2, 4, 5, 2] |
5 | 12 |
| 3 | 0 | [1, 2, 3, 1] |
3 | 15 |
若程式由左往右走訪,則依序加上 3 + 5 + 7,結果同樣是 15。
演算法步驟
- 將
nums的每一列各自按照遞增順序排序。 - 初始化總分
score = 0。 - 走訪每一欄
j,找出所有列在該欄的最大值。 - 將這個最大值加到
score。 - 回傳
score。
C++ 實作
class Solution {
public:
int matrixSum(vector<vector<int>>& nums) {
int m = nums.size();
int n = nums[0].size();
for (auto& row : nums) {
sort(row.begin(), row.end());
}
int score = 0;
for (int j = 0; j < n; ++j) {
int columnMax = 0;
for (int i = 0; i < m; ++i) {
columnMax = max(columnMax, nums[i][j]);
}
score += columnMax;
}
return score;
}
};
auto& row 使用參考,才能直接排序矩陣中的每一列。由於所有元素都非負,columnMax 可以初始化為 0。
Python 實作
class Solution:
def matrixSum(self, nums: List[List[int]]) -> int:
m, n = len(nums), len(nums[0])
for row in nums:
row.sort()
score = 0
for j in range(n):
column_max = max(nums[i][j] for i in range(m))
score += column_max
return score
兩份實作都會直接修改輸入矩陣中各列的順序。
正確性說明
將每列遞增排序後,以 a[i][j] 表示第 i 列、第 j 欄的值。
第一輪移除每列的最大值,也就是 a[i][n - 1]。移除後,下一輪的最大值就是 a[i][n - 2]。依此類推,第 k 輪(從 1 開始)會從每列移除 a[i][n - k]。即使有重複值,排序後的取出順序仍然符合題意。
因此,第 k 輪的得分恰好是排序後第 n - k 欄的最大值。經過 n 輪,每一欄都恰好貢獻一次最大值。
演算法累加了所有欄的最大值,與題目每一輪得分的總和相同,因此會回傳正確答案。
複雜度分析
令 m 為列數、n 為每列的元素數量。
- 時間複雜度:排序所有列需要 $O(mn \log n)$,掃描所有欄需要 $O(mn)$,合計為 $O(mn \log n + mn)$。當
n >= 2時,可簡寫為 $O(mn \log n)$。 - 額外空間複雜度:掃描與累加只需 $O(1)$;若計入排序的輔助空間,C++ 的
std::sort一般使用 $O(\log n)$ 的堆疊空間,Python 的list.sort()最壞需要 $O(n)$ 的輔助空間。各列依序排序,因此不需要將這些空間再乘上m。
常見錯誤
- 直接對原矩陣逐欄取最大值:每列的最大值可能位於不同欄,必須先將每列排序,讓相同排名的元素對齊。
- 將每列最大值直接加總:每一輪只加上所有移除值中的一個最大值,而不是加上這一輪移除的全部數字。
- 把整個矩陣攤平後排序:題目要求每輪從每列各取一個值,必須保留元素所屬的列。
- 每一列使用不同排序方向:所有列必須使用相同方向,才能讓同一欄對應到同一輪。
- 忘記重設欄最大值:每處理新的一欄,都要重新初始化
columnMax,避免混入上一欄的結果。