大2D位矩阵中大小为HxW的最大子数组
伊戈尔
我有一个大的NxN位数组，其中有K个（其他均为零）。所有非零点的坐标都是已知的-换句话说，此NxN数组可以表示为K对数组，每个对包含非零点的x和y坐标。
给定HxW大小的子矩阵，我需要将其放在我的原始NxN数组上，以使其覆盖最非零的点。
输入：子矩阵的高度H和宽度W
输出： HxW子数组的x和y坐标在其自身内最多
之前曾回答过类似的问题：2D矩阵中大小为HxW的最大子数组，但是在我的问题中，由于N很大，所以有点复杂，在我的情况下：N = 60000，K <15000，H，W <10000。
即使创建的是位数组，创建60000x60000数组也将导致内存消耗。这就是为什么我想出用所有非零点表示该数组的想法：K对的一维数组。
我能想到的一切都是超级的内存和时间效率低下的问题，我正在寻找不会消耗我所有内存的解决方案。这是它的含义：输出将是点（4,3），因为从此处开始的HxW子数组包含最多的子数组。
缺口
这是一种算法，应该（可能会对其进行优化），并且对空间要求不高。它基于这样的理论，即任何具有最高非零和的子矩阵都必须在其左边缘上有一个点（否则，可能会有一个子矩阵在其右边具有更高的和）。因此，要找到最高的总和，我们将遍历每个非零点，并找到在其左边缘具有该点的所有子矩阵，将当前点右边每一行中的所有非零点求和子矩阵。O(k2*h)O(k*h*w)O(k)W
以下是该算法的python实现。它首先创建每行中的点的字典，然后按照描述在每个点上进行迭代，将非零点的总和存储在该行的右边，然后基于该点为每个子矩阵计算总和。如果总和大于当前最大值，则存储该值及其位置。请注意，这使用0索引列表，因此对于您的示例数据，最大数量为(2, 3)。
from collections import defaultdict
def max_subarray(n, nzp, h, w):
maxsum = 0
maxloc = (0, 0)
# create a dictionary of points in a row
nzpd = defaultdict(list)
for p in nzp:
nzpd[p[0]].append(p[1])
# iterate over each of the non-zero points, looking at all
# submatrixes that have the point on the left side
for p in nzp:
y, x = p
pointsright = [0] * n
for r in range(max(y-(h-1), 0), min(y+h, n)):
# points within w to the right of this column on this row
pointsright[r] = len([p for p in nzpd[r] if x <= p <= x+(w-1)])
# compute the sums for each of the possible submatrixes
for i in range(-h+1, h):
thissum = sum(pointsright[max(y+i, 0):min(y+i+h, n)])
if thissum > maxsum:
maxsum = thissum
maxloc = (y, x)
# adjust the position in case the submatrix would extend beyond the last row/column
maxloc = (min(n-h, maxloc[0]), min(n-w, maxloc[1]))
# print the max sum
print(f'{maxsum} found at location {maxloc}')
用法示例：
nzp = [(0, 6), (1, 9), (2, 3), (2, 4), (2, 5),
(3, 1), (3, 4), (3, 6), (4, 3), (4, 3),
(4, 10), (5, 5), (6, 4), (6, 8), (7, 5),
(8, 3), (10, 2), (10, 8), (11, 4), (11, 10)
]
max_subarray(12, nzp, 2, 4)
输出：
5 found at location (2, 3)
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
2D矩阵中大小为HxW的最大子数组
- 2
将任意大小的矩阵/ 2d数组合并为一个大的2d数组
- 3
查找2D阵列上的最大子像素
- 4
尝试将矩阵导入为2D数组
- 5
numpy将2D矩阵重塑为对称矩阵数组（3D数组）而没有循环
- 6
获取最大子矩阵的坐标
- 7
存储最大子矩阵的坐标
- 8
2D矩阵是指针数组吗？
- 9
从2D数组创建距离矩阵
- 10
大小为MxN的矩阵中大小为AxB的子矩阵的数量
- 11
大小为MxN的矩阵中大小为AxB的子矩阵的数量
- 12
最大子数组总和，使得总和为奇数
- 13
查找总和为0的最大子数组的长度
- 14
A x B大小的所有2D子数组的最大值
- 15
作为单位矩阵的最大子矩阵
- 16
Java 2d数组的大小
- 17
使用 KNN 减少 2D 中的矩阵大小
- 18
在gcc 4.2.1上指向2d数组的指针的大小为8的原因是什么？
- 19
将对称矩阵（2D数组）的上/下三角部分转换为1D数组，并将其返回为2D格式
- 20
数组中大小为k的最小词典顺序
- 21
如何将2d numpy数组转换为二进制指标矩阵以获取最大值
- 22
在使用2d数组创建的矩阵中，是否可以标记出哪三列和三列的总和最大？
- 23
问题开始最大子数组
- 24
Python的最大子数组总和
- 25
使用javascript的最大子数组
- 26
2D数组数据为空？
- 27
如何检查2D矩阵是否为空？
- 28
如何输入矩阵样式的txt文件，而不是为C ++定义我自己的int 2D数组
- 29
使用空值创建2D矩阵坐标（数组）
我来说两句