LeetCode（Sorting)2500. Delete Greatest Value in Each Row

╰半夏微凉° 2023-09-23 23:31 87阅读 0赞

# 1.问题 #

You are given an m x n matrix grid consisting of positive integers.

Perform the following operation until grid becomes empty:

*  Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.
 *  Add the maximum of deleted elements to the answer.  
    Note that the number of columns decreases by one after each operation.

Return the answer after performing the operations described above.

Example 1:

> Input: grid = \[\[1,2,4\],\[3,3,1\]\]  
> Output: 8  
> Explanation: The diagram above shows the removed values in each step.
> 
>  *  In the first operation, we remove 4 from the first row and 3 from the second row (notice that, there are two cells with value 3 and we can remove any of them). We add 4 to the answer.
>  *  In the second operation, we remove 2 from the first row and 3 from the second row. We add 3 to the answer.
>  *  In the third operation, we remove 1 from the first row and 1 from the second row. We add 1 to the answer.  
>     The final answer = 4 + 3 + 1 = 8.

Example 2:

> Input: grid = \[\[10\]\]  
> Output: 10  
> Explanation: The diagram above shows the removed values in each step.
> 
>  *  In the first operation, we remove 10 from the first row. We add 10 to the answer.  
>     The final answer = 10.

Constraints:

*  m == grid.length
 *  n == grid\[i\].length
 *  1 <= m, n <= 50
 *  1 <= grid\[i\]\[j\] <= 100

# 2. 解题思路 #

## 方法1： ##

> 1.grid以升序排序  
> 2.遍历循环，grid\[0\].length（就是行的长度）和grid.length（列的长度）进行遍历，找出列的元素最大值，将值相加  
> 3.返回结果

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int deleteGreatestValue(int[][] grid) {
        
            int result = 0;
            for (int[] row : grid) {
        //1.grid以升序排序
                Arrays.sort(row);
            }
            for (int i = 0; i < grid[0].length; i++) {
        //2.遍历循环，grid[0].length（就是行的长度）和grid.length（列的长度）进行遍历，找出列的元素最大值，将值相加
                int max = 0;
                for (int j = 0; j < grid.length; j++) {
        
                    max = Math.max(max, grid[j][i]);
                }
                result += max;
            }
    
            return result;//3.返回结果
        }
    }

> 解题思路基本相同

class Solution {
        
        public int deleteGreatestValue(int[][] grid) {
        
            for(int i=0; i<grid.length; i++)    Arrays.sort(grid[i]);
            int res = 0;
            for(int i=0; i<grid[0].length; i++){
        
                int max = 0;
                for(int j=0; j<grid.length; j++)    
                    max = Math.max(max, grid[j][i]);
                res += max;
            }
            return res;
        }
    }