文档章节

矩阵(最大值)的范围 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
博文 561
码字总数 333804
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

内存模型是怎么解决缓存一致性的?

在再有人问你Java内存模型是什么,就把这篇文章发给他。这篇文章中,我们介绍过关于Java内容模型的来龙去脉。 我们在文章中提到过,由于CPU和主存的处理速度上存在一定差别,为了匹配这种差距...

Java填坑之路
13分钟前
1
0
vue-cli 3.0 初体验

最近复习了下vue,突然发现vue-cli已经更新到3.0版本了,并且变化蛮大,看来要不停的学习,真是一入前端深似海。 安装步骤: 1、全局安装 npm install -g @vue/cli Vue CLI 的包名称由 vue-...

tianyawhl
14分钟前
0
0
Angular进阶之路

【初级】会写页面,能出东西。 给定环境和 rest API,不用第三方库,能在十分钟内完成一个 master/detail 结构的带路由的应用(可以不管美观)。 知识点:Angular CLI、组件、路由、HTTP 服务...

陆小七的主页
17分钟前
0
0
Redis缓存数据库安全加固指导(一)

背景 在众多开源缓存技术中,Redis无疑是目前功能最为强大,应用最多的缓存技术之一,参考2018年国外数据库技术权威网站DB-Engines关于key-value数据库流行度排名,Redis暂列第一位,但是原生...

中间件小哥
17分钟前
0
0
百万级数据mysql分区

1. 什么是表分区? 表分区,是指根据一定规则,将数据库中的一张表分解成多个更小的,容易管理的部分。从逻辑上看,只有一张表,但是底层却是由多个物理分区组成。 2. 表分区与分表的区别 分表...

罗文浩
20分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部