Ricky.L的随笔
0%

LeetCode.304.二维区域和检索 - 矩阵不可变（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.304.二维区域和检索 - 矩阵不可变（中等）

给定一个二维矩阵 matrix，以下类型的多个请求：

  • 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
    实现 NumMatrix 类：
  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

题解

与LeetCode.1314.矩阵区域和思路相同。

NumMatrix.sumRegion()要想做到O(1)时间复杂度查询，就要提前计算好二位前缀和。

设preSum[i][j]为[0, 0]到[i, j]矩形区域所有元素和。

求矩形区域d的元素和

1
2
3
4
5
a a a b b b b b   
a a a b b b b b
c c c d d d d d
c c c d d d d d
c c c d d d d d

区域d所有元素和 = 整个区域所有元素和 - 区域a所有元素和- 区域b所有元素和 - 区域c所有元素和

设矩形d左上角坐标(x1, y1)，右下角坐标(x2, y2)。
整个区域所有元素和 = preSum[x2][y2]
区域a所有元素和 + 区域b所有元素和 = preSum[x1 - 1][y2]
区域a所有元素和 + 区域c所有元素和 = preSum[x2][y1 - 1]

所以:
区域d所有元素和 = preSum[x2][y2] - preSum[x1 - 1][y2] - preSum[x2][y1 - 1] + preSum[x1 - 1][y1 - 1]

遇到边界特殊处理一下就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class NumMatrix(matrix: Array<IntArray>) {

    private val m = matrix.size
    private val n = matrix[0].size

    val preSum = Array(m) { IntArray(n) { 0 } }

    init {
        // 求二维前缀和
        preSum[0][0] = matrix[0][0]
        for (j in 1 until n) {
            preSum[0][j] = preSum[0][j - 1] + matrix[0][j]
        }
        for (i in 1 until m) {
            preSum[i][0] = preSum[i - 1][0] + matrix[i][0]
        }
        for (i in 1 until m) {
            for (j in 1 until n) {
                val left = preSum[i][j - 1]
                val top = preSum[i - 1][j]
                val leftTop = preSum[i - 1][j - 1]
                preSum[i][j] = left + top - leftTop + matrix[i][j]
            }
        }
    }

    fun sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int {
        val all = preSum[row2][col2]
        val left = if (col1 == 0) 0 else preSum[row2][col1 - 1]
        val top = if (row1 == 0) 0 else preSum[row1 - 1][col2]
        val leftTop = if (row1 == 0 || col1 == 0) 0 else preSum[row1 - 1][col1 - 1]
        return all - left - top + leftTop
    }

}