Algorithm

[LeetCode 598] Range Addition II [Java] [Runtime : 6MS]

顿搜

2017-09-17

0 评论

540 阅读

正在检测是否收录...

09/17

1. Description

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 Mi 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.

2. Runtime Distribution

3. Submission Details

4. Example

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.

5. Code

public int maxCount(int m, int n, int[][] ops) {
    if (m <= 0 || n <= 0 || ops == null) {
        return 0;
    }

    int minRow = m;
    int minCol = n;
    for (int i = 0; i < ops.length; i++) {
        if (minRow > ops[i][0]) {
            minRow = ops[i][0];
        }
        if (minCol > ops[i][1]) {
            minCol = ops[i][1];
        }
    }

    return minRow * minCol;
}

6.Test

public class LeetCode0598 {
    public int maxCount(int m, int n, int[][] ops) {
        if (m <= 0 || n <= 0 || ops == null) {
            return 0;
        }

        int minRow = m;
        int minCol = n;
        for (int i = 0; i < ops.length; i++) {
            if (minRow > ops[i][0]) {
                minRow = ops[i][0];
            }
            if (minCol > ops[i][1]) {
                minCol = ops[i][1];
            }
        }

        return minRow * minCol;
    }

    public static void main(String[] args) {
        LeetCode0598 leetcode = new LeetCode0598();
        int ops[][] = { { 2, 2 }, { 3, 3 } };

        System.out.println(leetcode.maxCount(3, 3, ops));
    }
}

Matrix

朗读