【LetMeFly】2679.矩陣中的和：排序 + 模擬

力扣題目鏈接：https://leetcode.cn/problems/sum-in-a-matrix/

給你一個下標從 0?開始的二維整數(shù)數(shù)組?nums?。一開始你的分數(shù)為?0?。你需要執(zhí)行以下操作直到矩陣變?yōu)榭眨?/p>

1. 矩陣中每一行選取最大的一個數(shù)，并刪除它。如果一行中有多個最大的數(shù)，選擇任意一個并刪除。
2. 在步驟 1 刪除的所有數(shù)字中找到最大的一個數(shù)字，將它添加到你的 分數(shù)?中。

請你返回最后的 分數(shù)?。

?

示例 1：

輸入：nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]
輸出：15
解釋：第一步操作中，我們刪除 7 ，6 ，6 和 3 ，將分數(shù)增加 7 。下一步操作中，刪除 2 ，4 ，5 和 2 ，將分數(shù)增加 5 。最后刪除 1 ，2 ，3 和 1 ，將分數(shù)增加 3 。所以總得分為 7 + 5 + 3 = 15 。

示例 2：

輸入：nums = [[1]]
輸出：1
解釋：我們刪除 1 并將分數(shù)增加 1 ，所以返回 1 。

?

提示：

• 1 <= nums.length <= 300
• 1 <= nums[i].length <= 500
• 0 <= nums[i][j] <= 103

方法一：排序 + 模擬

其實只需要按照題目的意思進行模擬即可。每次在每一行中選擇一個未選擇過的最大的數(shù)，在所有行被選出的數(shù)中，將最大的那個累加到答案中。

那么唯一的問題是：如何快速選取某一行中，未被選擇過的數(shù)中最大的數(shù)。

其實很簡單，我們只需要將矩陣每一行從小到大排序，這樣對于某一行，只需要從后往前選擇就可以了。

• 時間復雜度$O(nm\log m)$，其中$size(nums)=n\times m$
• 空間復雜度$O(m\times m)$

AC代碼

C++

class Solution {
public:
    int matrixSum(vector<vector<int>>& nums) {
        int n = nums.size(), m = nums[0].size();
        for (int i = 0; i < n; i++) {
            sort(nums[i].begin(), nums[i].end());
        }
        int ans = 0;
        for (int j = m - 1; j >= 0; j--) {
            int M = 0;
            for (int i = 0; i < n; i++) {
                M = max(M, nums[i][j]);
            }
            ans += M;
        }
        return ans;
    }
};

Python

# from typing import List

class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        n, m = len(nums), len(nums[0])
        for line in nums:
            line.sort()
        ans = 0
        for j in range(m - 1, -1, -1):
            M = 0
            for i in range(n):
                M = max(M, nums[i][j])
            ans += M
        return ans

同步發(fā)文于CSDN，原創(chuàng)不易，轉載請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/131526894文章來源地址http://www.zghlxwxcb.cn/news/detail-520612.html

到了這里，關于LeetCode 2679. 矩陣中的和的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！