2023年7月27日每日一题--2500. 删除每行中的最大值

leetcode链接： 2500. 删除每行中的最大值

题目分析

对于数组，先按照行进行排序，然后从最大数值的部分按列求取最大值，将最大值添加到结果中。

方案一

class Solution {
    public int deleteGreatestValue(int[][] grid) {
        int result = 0;

        for (int i = 0; i < grid.length; i++) { // 对行进行排序
            Arrays.sort(grid[i]);
        }

        for (int i = grid[0].length - 1; i >= 0; i--) { // 对每一列进行遍历
            int max = 0;
            for (int j = 0; j < grid.length; j++) { // 求取每一列中的最大值
                max = max > grid[j][i] ? max : grid[j][i];
            }
            result += max;
        }

        return result;
    }
}

结果

解答成功:
执行耗时:2 ms,击败了100.00% 的Java用户
内存消耗:41.8 MB,击败了64.07% 的Java用户

分析

时间复杂度：
O( n * m * log(m) )
Arrays.sort() 使用的是归并排序的时间复杂度为n*log(n)。 https://blog.csdn.net/weixin_44065652/article/details/122177175

空间复杂度：
O( 1 )

方案二

官方题解

https://leetcode.cn/problems/delete-greatest-value-in-each-row/solution/shan-chu-mei-xing-zhong-de-zui-da-zhi-by-6fh9/

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

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/delete-greatest-value-in-each-row/solution/shan-chu-mei-xing-zhong-de-zui-da-zhi-by-6fh9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。