福建路桥建设有限公司网站,互联网营销师,快速网站建设公司哪家好,sem推广是什么意思呢1 区域和检索 - 数组不可变
1.1 题目描述 题目链接#xff1a;https://leetcode.cn/problems/range-sum-query-immutable/
1.2 思路分析 最朴素的想法是存储数组 nums 的值#xff0c;每次调用 sumRange 时#xff0c;通过循环的方法计算数组 nums 从下标 iii 到下标 jjj …1 区域和检索 - 数组不可变
1.1 题目描述 题目链接https://leetcode.cn/problems/range-sum-query-immutable/
1.2 思路分析 最朴素的想法是存储数组 nums 的值每次调用 sumRange 时通过循环的方法计算数组 nums 从下标 iii 到下标 jjj 范围内的元素和需要计算 j−i1j−i1j−i1 个元素的和。由于每次检索的时间和检索的下标范围有关因此检索的时间复杂度较高如果检索次数较多则会超出时间限制。 由于会进行多次检索即多次调用 sumRange因此为了降低检索的总时间应该降低 sumRange 的时间复杂度最理想的情况是时间复杂度 O(1)O(1)O(1)。为了将检索的时间复杂度降到 O(1)O(1)O(1)需要在初始化的时候进行预处理。 注意到当 i≤ji≤ji≤j 时sumRange(i,j) 可以写成如下形式
sumRange(i,j)∑kijnums[k]∑k0jnums[k]−∑k0i−1nums[k]\begin{aligned} \operatorname{sum} \operatorname{Range}(i, j) \\ \sum_{ki}^j n u m s[k] \\ \sum_{k0}^j n u m s[k]-\sum_{k0}^{i-1} n u m s[k]\end{aligned}sumRange(i,j)ki∑jnums[k]k0∑jnums[k]−k0∑i−1nums[k] 由此可知要计算 sumRange(i,j)则需要计算数组 nums 在下标 jjj 和下标 i−1i−1i−1 的前缀和然后计算两个前缀和的差。 如果可以在初始化的时候计算出数组 nums 在每个下标处的前缀和 pre_sum即可满足每次调用 sumRange 的时间复杂度都是 O(1)O(1)O(1)。
示例代码
class NumArray:def __init__(self, nums: List[int]):self.pre_sum [0] # 便于计算累加和若直接分配数组空间计算效率更高for i in range(len(nums)):self.pre_sum.append(self.pre_sum[i] nums[i]) # 计算nums累加和def sumRange(self, left: int, right: int) - int:return self.pre_sum[right1] - self.pre_sum[left]下面以数组 [1, 12, -5, -6, 50, 3] 为例展示了求 pre_sum 的过程。 复杂度分析
时间复杂度初始化 O(n)O(n)O(n)每次检索 O(1)O(1)O(1)其中 nnn 是数组 nums 的长度。初始化需要遍历数组 nums 计算前缀和时间复杂度是 O(n)O(n)O(n)。每次检索只需要得到两个下标处的前缀和然后计算差值时间复杂度是 O(1)O(1)O(1)。空间复杂度O(n)O(n)O(n)其中 nnn 是数组 nums 的长度。需要创建一个长度为 n1n1n1 的前缀和数组。 2 二维区域和检索 - 矩阵不可变
2.1 题目描述 题目链接https://leetcode.cn/problems/range-sum-query-2d-immutable/
2.2 思路分析 这部分借鉴自笨猪爆破组的题解————从暴力法开始优化 「二维前缀和」做了什么事 | leetcode.304
1. 暴力法 对二维矩阵求子矩阵 (n∗m)(n*m)(n∗m) 的和。两重循环累加求和。 每次查询时间复杂度 O(n∗m)O(n∗m)O(n∗m)n和m是子矩阵的行数和列数。查询的代价大。
2. 第一步优化 上面的暴力法其实也分了 n 步第一行的求和到第 n 行的求和它们是 n 个一维数组。 昨天我们学习了一维前缀和我们可以对这n个一维数组求前缀和得到n个一维pre_sum数组。 为了节省查询的时间我们求出整个矩阵每一行的一维pre_sum数组 根据前缀和定义pre_sum[i]nums[0]nums[1]⋯nums[i]{pre}\_{sum}[i]nums[0]nums[1]\cdotsnums[i]pre_sum[i]nums[0]nums[1]⋯nums[i]求出前缀和下图红字 然后套用通式nums[i]⋯nums[j]pre_sum[j]−pre_sum[i−1]nums[i]\cdotsnums[j]pre\_sum[j]-pre\_sum[i-1]nums[i]⋯nums[j]pre_sum[j]−pre_sum[i−1] 即可求出粉色子阵列的和计算情况如下图。 可见如果想多次查询子阵列的和我们可以提前求出每一行数组的一维前缀和。 那么查询阶段求出一行子数组的求和就只是 O(1)O(1)O(1)查询 n 行的子阵列每次就查询花费 O(n)O(n)O(n)比 O(n2)O(n^2)O(n2) 好
3. 示例代码
class NumMatrix:def __init__(self, matrix: List[List[int]]):m, n len(matrix), len(matrix[0]) # 矩阵的行和列self.pre_sum [[0] for _ in range(m)] # 构造一维前缀和矩阵for i in range(m):for j in range(n):self.pre_sum[i].append(self.pre_sum[i][j]matrix[i][j])def sumRegion(self, row1: int, col1: int, row2: int, col2: int) - int:return sum([self.pre_sum[i][col21]-self.pre_sum[i][col1] for i in range(row1, row21)])4. 第二步优化 还可以继续优化吗 我们引入一个概念二维前缀和定义式如下 pre_sum[i][j] 表示左上角为 arr[0][0]右下角为 arr[i][j] 的阵列的求和. 我们把这个阵列拆分成四个部分如图中的色块。 要想求出 pre_sum[i][j]根据上图由容斥原理有 移项后
arr[i][j]pre_sum[i][j]pre_sum[i−1][j−1]−pre_sum[i−1][j]−pre_sum[i][j−1]arr[i][j] pre\_sum[i][j] pre\_sum[i-1][j-1] - pre\_sum[i-1][j] - pre\_sum[i][j-1]arr[i][j]pre_sum[i][j]pre_sum[i−1][j−1]−pre_sum[i−1][j]−pre_sum[i][j−1] 现在想求行 从 a 到 A列 从 b 到 B 的子阵列的和。叠加上式各种相消后。得 回到粉色子阵列求她的和就是如下图的 4 个 pre_sum 矩阵元素相加减。 问题来了怎么求出 pre_sum 二维阵列的每一项 就是用遍历原矩阵两层循环套下图的公式。 注意到上图黄字在 -1 位置上预置了 0只是为了让处于边界的 preSum 元素也能套用下面的通式。 两个关键式 pre_sum[i][j] 的定义式如下并且预置 pre-sum[-1][j] 和 pre_sum[i][-1] 为 0
preSum[i][j]∑x0i∑y0jarr[x][y]\operatorname{preSum}[i][j]\sum_{x0}^i \sum_{y0}^j \operatorname{arr}[x][y] preSum[i][j]x0∑iy0∑jarr[x][y] 求行从 a 到 A列从 b 到 B 的子阵列的和的通式 ∑iaA∑ibBarr[i][j]pre_sum[A][B]pre_sum[a−1][b−1]−pre_sum[A][b−1]−pre_sum[a−1][B]\sum_{ia}^A \sum_{ib}^B \operatorname{arr}[i][j]\operatorname{pre\_sum}[A][B]\operatorname{pre\_sum}[a-1][b-1]-\operatorname{pre\_sum}[A][b-1]-\operatorname{pre\_sum}[a-1][B] ia∑Aib∑Barr[i][j]pre_sum[A][B]pre_sum[a−1][b−1]−pre_sum[A][b−1]−pre_sum[a−1][B] 查询的时间复杂度降下来了 因此子阵列的求和都只需要访问二维 pre_sum 数组的四个值。 预处理阶段求出二维 pre_sum 数组需要花费 O(n∗m)O(n∗m)O(n∗m)n和m是子矩阵的行数和列数。 但之后每次查询就都是 O(1)O(1)O(1) 的时间复杂度
5. 调整 pre_sum 矩阵 为了减少特判的代码我们调整一下 pre_sum 矩阵原先 arr[i][j] 对应 pre_sum[i][j] 现在错开arr[i][j] 对应 pre_sum[i1][j1]。 如下图所示pre_sum 阵列会比原矩阵多一行一列为了让 pre_sum 的 -1 列 -1 行变成 0 行 0 列 现在 preSum[i][j] 的定义式改一下
pre_sum[i1][j1]∑x0i∑y0jarr[x][y]\operatorname{pre\_sum}[i1][j1]\sum_{x0}^i \sum_{y0}^j \operatorname{arr}[x][y] pre_sum[i1][j1]x0∑iy0∑jarr[x][y] 并且预置 pre_sum[0][j] 和 pre_sum[i][0] 为 0 求行从 a 到 A列从 b 到 B 的子阵列的和的通式改一下 ∑iaA∑ibBarr[i][j]pre_sum[A1][B1]pre_sum[a][b]−pre_sum[A1][b]−pre_sum[a][B1]\sum_{ia}^A \sum_{ib}^B \operatorname{arr}[i][j]\operatorname{pre\_sum}[A1][B1]\operatorname{pre\_sum}[a][b]-\operatorname{pre\_sum}[A1][b]-\operatorname{pre\_sum}[a][B1] ia∑Aib∑Barr[i][j]pre_sum[A1][B1]pre_sum[a][b]−pre_sum[A1][b]−pre_sum[a][B1]
6. 示例代码
class NumMatrix:def __init__(self, matrix: List[List[int]]):m, n len(matrix), len(matrix[0]) # 矩阵的行和列self.pre_sum [[0]*(n1) for _ in range(m1)] # 构造一维前缀和矩阵for i in range(m):for j in range(n):self.pre_sum[i1][j1] self.pre_sum[i1][j] self.pre_sum[i][j1] - self.pre_sum[i][j] matrix[i][j]def sumRegion(self, row1: int, col1: int, row2: int, col2: int) - int:return (self.pre_sum[row21][col21] - self.pre_sum[row1][col21] - self.pre_sum[row21][col1] self.pre_sum[row1][col1])7. 复杂度分析
时间复杂度初始化 O(mn)O(mn)O(mn)每次检索 O(1)O(1)O(1)其中 m 和 n 分别是矩阵 matrix 的行数和列数。初始化需要遍历矩阵 matrix 计算二维前缀和时间复杂度是 O(mn)O(mn)O(mn)。每次检索的时间复杂度是 O(1)O(1)O(1)。空间复杂度O(mn)O(mn)O(mn)其中m和n分别是矩阵 matrix 的行数和列数。需要创建一个 m1 行 n1 列的二维前缀和数组 pre_sum。 做题心得以后会不会延伸到张量呢更高维数的也是总结通式就比如三维是一个立方体依然是计算每个小立方体的和。
