【LeetCode】范围求和 IIJava 题解

HQ数字卡

关注

发布于: 3 小时前

题目描述

给定一个初始元素全部为 0，大小为 m*n 的矩阵 M 以及在 M 上的一系列更新操作。

操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b 的数组表示，含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1。

在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。

示例 1:
输入: m = 3, n = 3operations = [[2,2],[3,3]]输出: 4解释: 初始状态, M = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
执行完操作 [2,2] 后, M = [[1, 1, 0], [1, 1, 0], [0, 0, 0]]
执行完操作 [3,3] 后, M = [[2, 2, 1], [2, 2, 1], [1, 1, 1]]
M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/range-addition-ii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法每日一题是数组类题目，具体是范围求和。阅读题目，这是一个二维数组，ops 是一个操作数组，使具体的数组值加一。
首先，我们可以使用朴素解法，定义数组 m, n。然后遍历 ops 这个操作数组，并使用 hashMap 记录出现的值和值的次数。这种方法占用了较大的空间，不能通过所有的测试用例。
仔细思考一下，朴素解法的最终要求的是 ops 的交集部分，我们可以直接求 ops 的交集，思路就是分别求出 x, y 的最小值，最终 x * y 即位答案。实现详细代码如下：

通过代码

朴素算法

class Solution {    public int maxCount(int m, int n, int[][] ops) {        int ans = 0;        if (ops.length == 0) {            ans = m * n;        } else {            int[][] arr = new int[m][n];            int tempMax = 0;            Map<Integer, Integer> map = new HashMap<>();            for (int[] op : ops) {                for (int i = 0; i < op[0]; i++) {                    for (int j = 0; j < op[1]; j++) {                        arr[i][j] += 1;                        map.put(arr[i][j], map.getOrDefault(arr[i][j], 0) + 1);                        tempMax = Math.max(tempMax, arr[i][j]);                     }                }            }            ans = map.getOrDefault(tempMax, 0);        }
        return ans;    }}

复制代码

优化解法

class Solution {    public int maxCount(int m, int n, int[][] ops) {        int ans = 0;        if (ops.length == 0) {            ans = m * n;        } else {            int minX = Integer.MAX_VALUE;            int minY = Integer.MAX_VALUE;            for (int[] op : ops) {                minX = Math.min(minX, op[0]);                minY = Math.min(minY, op[1]);            }            ans = minX * minY;        }
        return ans;    }}

复制代码

总结

朴素解法的时间复杂度是 O(m * n), 空间复杂度 O(m * n)
优化解法的时间复杂度是 O(m * n), 空间复杂度 O(1)
坚持算法每日一题，加油！

发布于: 3 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/f66e15786a67e89d19476b2fc】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】范围求和 IIJava 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论