文档章节

矩阵(最大值)的范围 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;
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 10
博文 563
码字总数 334385
作品 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
数据转换

一.标准化的原因 通常情况下是为了消除量纲的影响。譬如一个百分制的变量与一个5分值的变量在一起怎么比较?只有通过数据标准化,都把它们标准到同一个标准时才具有可比性,一般标准化采用的...

readilen
2017/11/24
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

没有更多内容

加载失败,请刷新页面

加载更多

负载均衡的解决方案有哪些

负载均衡器服务可满足大型组织的需求,支持所有数据中心和跨数据中心高可靠性场景。 本地负载均衡,通过附带或者未附带持久性覆盖选项,Incapsula支持各种负载均衡算法,以优化服务器之间的流...

上树的熊
28分钟前
3
0
Java实现在线打开word文档加盖印章/盖章/签名功能

前言: 我们知道,大型一点的OA办公系统都会有很多在线处理office办公文档的需求。其中有一点也基本绕不开,那就是为文档盖章或添加手写签名来保护文档,让被盖章的文档不再被编辑。 在Java中...

山里的红杏
36分钟前
5
0
js控制输入正负数,小数点后保留两位

//限制数字function clearNoNum(obj){ //修复第一个字符是小数点 的情况. if(obj.value !=''&& obj.value.substr(0,1) == '.'){ obj.value=""; } obj.value ...

一直在成长的程序猿
38分钟前
2
0
动态代理

具体场景 为了使代理类与被代理类对第三方有相同的函数,代理类与被代理类一般实现一个公共的interface,定义如下 public interface Subject { void rent(); void hello(String s)...

wuyiyi
42分钟前
2
0
时间字段

我们看看这几个数据库中(mysql、oracle和sqlserver)如何表示时间 mysql数据库:它们分别是 date、datetime、time、timestamp和year。date :“yyyy-mm-dd”格式表示的日期值 time :“hh:...

DemonsI
44分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部