文档章节

矩阵(最大值)的范围 Range Addition II

叶枫啦啦
 叶枫啦啦
发布于 2017/06/26 18:27
字数 433
阅读 19
收藏 0

问题:

Given an m * n matrix M initialized with all 0's and several update operations.

Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.

You need to count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

Input: 
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation: 
Initially, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

After performing [2,2], M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]

After performing [3,3], M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

So the maximum integer in M is 2, and there are four of it in M. So return 4.

Note:

  1. The range of m and n is [1,40000].
  2. The range of a is [1,m], and the range of b is [1,n].
  3. The range of operations size won't exceed 10,000.

解决:

①只要找到二维坐标的第一个坐标的最小值和第二个坐标的最小值相乘即可;

public class Solution { //6ms
    public int maxCount(int m, int n, int[][] ops) {
        if(ops == null || ops.length == 0) return m * n;
        int minRow = Integer.MAX_VALUE;
        int minCol = Integer.MAX_VALUE;
        for (int op[] : ops) {
            if (minRow > op[0]) minRow = op[0]; 
            if (minCol > op[1]) minCol = op[1];
        }
        return minRow * minCol;
    }
}

② 我首先想到的是这种方法,按照题意依次将对应位置加1,然后遍历数组,查找与arr[0][0]相同的值的个数即可。但是出现了内存不足(Memory Limit Exceeded)。

public class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int[][] arr = new int[m][n];
        for(int[] op : ops){
            for(int i = 0;i < op[0];i ++){
                for(int j = 0;j < op[1];j ++){
                    arr[i][j] += 1;
                }
            }
        }
        int count = 0;
        for(int i = 0;i < m;i ++){
            for(int j = 0;j < n;j ++){
                if(arr[i][j] == arr[0][0]) count ++;
            }
        }
        return count;
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 12
博文 569
码字总数 354997
作品 0
海淀
私信 提问
Search a 2D Matrix II【原创】

Search a 2D Matrix II: python学了还么两周可能有些地方写的很新手大家不要笑我 解题思路: 首先当数组为1维数组时if in 直接查找即可 当为 m x n 维数组时: matrix为行增列增的有序矩阵 ...

big_cat
2015/07/27
0
0
验证码识别技术二——北京市

大约8个月前,曾经写过一篇关于验证码识别的文章,很久没再更新了,今天再来介绍一下北京市的验证码识别技术。 1、验证码样例 北京市验证码有两种类型,第一种类型是四个字母或数字混合类,如...

东方神剑
2016/11/27
170
0
Opencv常见用法和常见错误(一)

一. 读取中文的路径的图像 使用Opencv错误的读法如下: 将会产生如下错误 正确的读法如下: 在读取图像的时候加入两个头文件: 可以得到结果图: 二. 申请一个全1或者全0矩阵 三. 矩阵的点乘和...

小明知道
2015/07/30
0
0
初学数模-MATLAB Quick Start! Part II

让我们先从一张图片说起: 这幅画是由德国大画家丢勒(Albrecht Dürer)所画,其中布满了数学符号。在右上方的窗户上,你会发现那是一个矩阵。我们就从这里开始。 那么,在这幅名画中出现的...

不高不富不帅的陈政_
2015/09/15
187
0
GUAVA常用方法总结整理(list map string concurrent file)

1.对字符串的操作: 2.FluentIterable迭代器: Guava提供了可以在Iterator中进行处理的功能更丰富的迭代器, 其实就像是加了一个代理, 增加一些功能。 3.Lists列表: Table矩阵: 使用Guava...

李矮矮
2016/09/17
106
0

没有更多内容

加载失败,请刷新页面

加载更多

PHP生成CSV之内部换行

当我们使用PHP将采集到的文件内容保存到csv文件时,往往需要将采集内容进行二次过滤处理才能得到需要的内容。比如网页中的换行符,空格符等等。 对于空格等处理起来都比较简单,这里我们单独...

豆花饭烧土豆
37分钟前
1
0
使用 mjml 生成 thymeleaf 邮件框架模板

发邮件算是系统开发的一个基本需求了,不过搞邮件模板实在是件恶心事,估计搞过的同仁都有体会。 得支持多种客户端 支持响应式 疼彻心扉的 outlook 多数客户端只支持 inline 形式的 css 布局...

郁也风
40分钟前
4
0
让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字

让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字: 作者:孙冬梅;以前读韩国前总统朴槿惠的著作《绝望锻炼了我》时,里面有一句话令我印象深刻,她说“在我最困难的时期,...

原创小博客
今天
3
0
JAVA-四元数类

public class Quaternion { private final double x0, x1, x2, x3; // 四元数构造函数 public Quaternion(double x0, double x1, double x2, double x3) { this.x0 = ......

Pulsar-V
今天
17
0
Xshell利用Xftp传输文件,使用pure-ftpd搭建ftp服务

Xftp传输文件 如果已经通过Xshell登录到服务器,此时可以使用快捷键ctrl+alt+f 打开Xftp并展示Xshell当前的目录,之后直接拖拽传输文件即可。 pure-ftpd搭建ftp服务 pure-ftpd要比vsftp简单,...

野雪球
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部