[Swift]LeetCode598. 范围求和 II | Range Addition II

it2022-05-06  4

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号:山青咏芝(shanqingyongzhi)➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/)➤GitHub地址:https://github.com/strengthen/LeetCode➤原文地址:https://www.cnblogs.com/strengthen/p/10450437.html ➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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:

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

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

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

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

示例 1:

输入: m = 3, n = 3 operations = [[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。

注意:

m 和 n 的范围是 [1,40000]。a 的范围是 [1,m],b 的范围是 [1,n]。操作数目不超过 10000。
Runtime: 44 ms Memory Usage: 19.1 MB 1 class Solution { 2 func maxCount(_ m: Int, _ n: Int, _ ops: [[Int]]) -> Int { 3 var m = m 4 var n = n 5 for op in ops 6 { 7 m = min(m, op[0]) 8 n = min(n, op[1]) 9 } 10 return m * n 11 } 12 }

56ms

1 class Solution { 2 func maxCount(_ m: Int, _ n: Int, _ ops: [[Int]]) -> Int { 3 var minX = m 4 var minY = n 5 for operation in ops where operation[0] > 0 && operation[1] > 0 { 6 minX = min(minX, operation[0]) 7 minY = min(minY, operation[1]) 8 } 9 10 return minX * minY 11 } 12 }

116ms

1 class Solution { 2 func maxCount(_ m: Int, _ n: Int, _ ops: [[Int]]) -> Int { 3 guard !ops.isEmpty else { 4 return m * n 5 } 6 7 var a = Int.max 8 var b = Int.max 9 for op in ops { 10 a = min(op.first!, a) 11 b = min(op.last!, b) 12 } 13 14 return a * b 15 } 16 }

 

转载于:https://www.cnblogs.com/strengthen/p/10450437.html


最新回复(0)